Do K33-Free Latin Squares Exist?

2023/04/14 by Krotov, Aleksandr D., Krotov, Denis S.
#05B15 #05E30 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2304.07157

Abstract

We discuss the problem of existence of latin squares without a substructure consisting of six elements (r₁,c₂,l₃), (r₂,c₃,l₁), (r₃,c₁,l₂), (r₂,c₁,l₃), (r₃,c₂,l₁), (r₁,c₃,l₂). 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] 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. Keywords: latin square; transversal; trade; pattern avoiding; eigenfunction; universally noncommutative loops.

Related

• Latin Squares whose transversals intersect in unusual ways
• Quasi-transversal in Latin Squares
• Latin Polytopes
• Latin Squares whose transversals share many entries
• Fun with Latin Squares