Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles (Q1277147): Difference between revisions

A Latin squares of order \(n\) is pan-Hamiltonian if every pair of rows determines a permutation consisting of a single cycle of length \(n\). This is equivalent to saying that the Latin square contains no proper subrectangles. A Latin square is atomic if its six conjugates are all pan-Hamiltonian. Also, there exists a pan-Hamiltonian Latin square of order \(n\) if and only if the complete bipartite graph \(K_{n,n}\) has a perfect 1-factorization. Pan-Hamiltonian Latin squares exist of orders \(n= p\) and \(n= 2p-1\), where \(p\) is prime; there is no such square of even order \(n\geq 4\). If the complete graph \(K_{n+ 1}\) has a perfect 1-factorization, then so does \(K_{n,n}\), and due to the conjectured existence of a perfect 1-factorization of \(K_n\) for all even \(n\), the author conjectures the existence of pan-Hamiltonian Latin squares of all odd orders \(n\). The Latin square \(C_p\) of order \(p\), where \(p\) is prime, consisting of the Caylay table for the cyclic group of order \(p\), is atomic, and the author produces an atomic square of order \(p\) outside the main class of \(C_p\) provided 2 is a primitive root modulo \(p\). The author notes the existence of atomic squares of composite order, citing the square of order 27 constructed from the perfect 1-factorization of \(K_{28}\), but knows of no non-prime power order atomic squares. The author also gives a catalog of pan-Hamiltonian Latin squares of orders up through 9.