View PDF HTML (experimental)

Abstract:We discuss the problem of the existence of latin squares without a substructure consisting of six elements $(r_1,c_2,l_3)$, $(r_2,c_3,l_1)$, $(r_3,c_1,l_2)$, $(r_2,c_1,l_3)$, $(r_3,c_2,l_1)$, $(r_1,c_3,l_2)$. Equivalently, the corresponding latin square graph does not have an induced subgraph isomorphic to $K_{3,3}$. The exhaustive search [Brouwer, Wanless. Universally noncommutative loops. 2011] shows that no such latin squares exist for orders $3$, $4$, $5$, $6$, $7$, $9$, $10$, $11$ and there are only two $K_{3,3}$-free latin squares of order $8$, up to equivalence. We repeat the search, establishing also the number of $K_{3,3}$-free latin $m$-by-$n$ rectangles for each $m$ and $n$ less than or equal to $11$. As a switched combination of two orthogonal latin squares of order $8$, we construct a $K_{3,3}$-free (universally noncommutative) latin square of order $16$.
We also consider a similar problem for orthogonal latin squares, proving that there are both $K_{4,4}$-free and non-$K_{4,4}$-free linear pairs of orthogonal latin squares for each odd prime-power order larger than $5$.
Keywords: latin square; orthogonal latin squares; transversal; trade; pattern avoidance; eigenfunction.

Submission history

From: Denis Krotov [view email]
[v1] Fri, 14 Apr 2023 14:29:35 UTC (15 KB)
[v2] Sat, 24 Jan 2026 09:17:34 UTC (24 KB)
[v3] Mon, 31 Aug 2026 15:54:41 UTC (30 KB)