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$.

Cite: Krotov A.D. , Krotov D.S.
Do $K_{3,3}$-free Latin squares exist?
Discrete Mathematics. 2027. V.350. N1. 115402 :1-12. DOI: 10.1016/j.disc.2026.115402 WOS Scopus OpenAlex

Dates:

Submitted:	Jan 24, 2026
Accepted:	Aug 25, 2026
Published online:	Sep 8, 2026

Identifiers:

≡ Web of science:	WOS:001873987100001
≡ Scopus:	2-s2.0-105049610321
≡ OpenAlex:	W4366206402

Altmetrics: