Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups

Raúl M. Falcón, Rebecca J. Stones

Research output: Contribution to journalArticleResearchpeer-review

16 Citations (Scopus)

Abstract

An r×s partial Latin rectangle (lij) is an r×s matrix containing elements of {1,2,…,n}∪{⋅} such that each row and each column contain at most one copy of any symbol in {1,2,…,n}. An entry is a triple (i,j,lij) with lij≠⋅. Partial Latin rectangles are operated on by permuting the rows, columns, and symbols, and by uniformly permuting the coordinates of the set of entries. The stabilizers under these operations are called the autotopism group and the autoparatopism group, respectively. We develop the theory of symmetries of partial Latin rectangles, introducing the concept of a partial Latin rectangle graph. We give constructions of m-entry partial Latin rectangles with trivial autotopism groups for all possible autoparatopism groups (up to isomorphism) when: (a) r=s=n, i.e., partial Latin squares, (b) r=2 and s=n, and (c) r=2 and s≠n.

Original languageEnglish
Pages (from-to)1242-1260
Number of pages19
JournalDiscrete Mathematics
Volume340
Issue number6
DOIs
Publication statusPublished - Jun 2017
Externally publishedYes

Keywords

  • Autoparatopism
  • Autotopism
  • Latin square
  • Partial Latin rectangle
  • Partial Latin rectangle graph

Cite this