Refining invariants for computing autotopism groups of partial Latin rectangles (Q2305926): Difference between revisions

A partial Latin rectangle is a partially filled matrix with the property that no symbol is repeated within any row or column. In this paper, an additional requirement is imposed for convenience, namely that no row or column should be empty. An autotopism of a partial Latin rectangle \(R\) is a triple of permutations applied to the rows, columns and symbols of \(R\), respectively, which leaves \(R\) unchanged. The set of such operations is the autotopism group of \(R\). The purpose of the present work is to study how to compute the autotopism group of partial Latin rectangles efficiently. In particular, the authors are interested in autotopism invariants that can be calculated quickly and which partition the rows, column and symbols as finely as possible. The finest possible partitions are those induced by the orbits of the autotopism group, and the authors report some computational evidence that their invariants reach this theoretical limit in almost all cases. However, they do acknowledge that there are some pathological examples, such as atomic Latin squares, for which their invariants perform very badly. The first invariant that they study is the strong entry invariant introduced by two of the authors in an earlier paper in the same journal [Discrete Math. 340, No. 6, 1242--1260 (2017; Zbl 1422.05027)]. The second invariant is based on the cyclic structure often used for studying Latin squares, but now generalised to partial Latin rectangles.