Реферат: We discuss the problem of 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)$, where $(r, c, l)$ means that the cell in the $r$th row and $c$th column contains the symbol $l$. Equivalently, the corresponding latin square graph does not have an induced subgraph isomorphic to $K_{3,3}$. The exhaustive search [1] says that there are no such latin squares of order from $3$ to $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 latin $m$-by-$n$ rectangles for each $m$ and $n$ less 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$. The problem can be generalized to the study of $K_{k+2,k+2}$-free collections of $k$ mutually orthogonal latin squares. For example, among the two linear pairs of orthogonal latin squares over GF$(7)$, one is $K_{4,4}$-free and the other is not. This is joint work with Aleksandr Krotov. [1] A. Brouwer, I. M. Wanless, Universally noncommutative loops, Bull. Inst. Comb. Appl. 61, 2011, 113–115.

Библиографическая ссылка: Krotov D.
On latin-square graphs avoiding K33
Autumn Workshop on Algebraic Combinatorics November 8-9, 2025, Shijiazhuang, China 08-09 Nov 2025