# graph built from orthogonal Latin Squares

I've asked the following question on MathExchange site, with a bounty, with no answer or comments. Maybe I would have additional comments here. The problem came to be while reading some articles on finite geometry. I began wondering if anybody had previously studied this.

Reminder on Latin Square: Given a set $$S$$ of $$n$$ elements (we will use $$[n]$$ in the following for simplicity), a Latin square $$L$$ is a function $$L : [n]\times [n] \to S$$, i.e., an $$n\times n$$ array with elements in $$S$$, such that each element of $$S$$ appears exactly once in each row and each column. For example,

Let $$L_1$$ and $$L_2$$ be two Latin squares over the ground sets $$S_1$$, $$S_2$$ respectively. They are called orthogonal if for every $$(x_1, x_2) \in S_1 \times S_2$$ there exists a unique $$(i,j)\in [n] \times [n]$$ such that $$L_1(i,j) = x_1$$ and $$L_2(i,j) = x_2$$. For example, the following are two orthogonal Latin squares of order 3.

It is known that there at most $$n-1$$ mutually orthogonal Latin squares of order $$n$$, and that the bound is achieved if and only there exist an affine plane of order $$n$$.

The graph definition: I'm building a graph $$G_n$$ with vertex set the Latin squares of order $$n$$ and two vertices are adjacent iff the Latin squares are orthogonal.

I want to understand some properties of this graph. For simplicity I consider the squares up to permutation of $$[n]$$, hence w.l.o.g. all my squares have for first line $$\{1,2,\ldots,n\}$$. Indeed if I call $$H_n$$ the graph not up to permutations, then $$H_n$$ is the $$n!$$ graph blowup of $$G_n$$, or using the Tensor product $$H_n = G_n \times K_{n!}$$ As I'm mainly interested in the chromatic number of my graph, and we know that $$\chi(H_n)\leq \min\{\chi(G_n) ; n!\}$$, I will study only $$G_n$$.

For instance $$G_2=K_1$$, $$G_3=K_2$$.

I know that :

• It's trivial that $$G_n$$ is not complete.
• If there exist an affine plane of order $$n$$ then $$G_n$$ contains $$K_{n-1}$$ as a subgraph, and $$\chi(G_n)\geq n-1$$.

• $$G_4$$ is made of 2 disjoint $$K_3$$ and 18 isolated vertices, for a total of 24 Latin squares.

• $$G_5$$ is made of 36 disjoint $$K_4$$ and 1200 isolated vertices, for a total of 1344 Latin squares.

• The case $$n=6$$ would be the first interesting case, as there are no affine plance of order 6, hence we will find no $$K_5$$ in $$G_6$$. It is known since 1901 (from Tarry hand checking all Latin squares of order 6) that no two Latin squares of order 6 are mutually orthogonal. So $$G_6$$ is made of only isolated vertices (with 1,128,960 vertices).

• It is also know that the case $$n=2$$ and $$n=6$$ are the only one with only isolated vertices. (see design theory by Beth, Jingnickel and Lenz).

• From the article "Monogamous Latin Square by Danziger, Wanless and Webb, available on Wanless website here. The authors show that for all $$n > 6$$, if $$n$$ is not of the form $$2p$$ for a prime $$p \geq 11$$, then there exists a Latin square of order $$n$$ that possesses an orthogonal mate but is not in any triple of Mutually Orthogonal Latin Squares. Therefore our graph $$G_n$$ will have some isolated $$K_2$$

I wonder the following :

• What is the maximum degree of $$G_n$$ ? We know that we have at most $$n-1$$ mutually orthogonal latin squares, but to how many squares can one square be orthogonal (still up to permutation)?
• Do we have any other info on the chromatic number, not coming from the property $$\chi(G_n)\leq \Delta+1$$.
• Can $$G_n$$ contains an induce $$k$$-cycle with $$k>3$$ (i.e. chordless cycle)?

• The stronger statement would be the following conjecture

Conjecture : for any $$n$$, $$G_n$$ is the disjoint union of complete subgraphs (of different sizes).

Or said otherwise, the orthogonal relation is transitive (when restricted to our Latin squares with first row fixed at $$\{1,2,\ldots,n\}$$.

I would welcome any intuition, direction for some articles, or any known additional facts.

• On order 10 there are plenty of squares with more than one orthogonal mate, but there are no triples known. So your conjecture is false. Apr 14, 2020 at 4:31
• @BrendanMcKay ok thanks for the info. I'm looking at Prof. Wanless website and references in order to get a better understanding of my others questions. Thanks Apr 14, 2020 at 4:47
• I just realised that the coloring problem is quite trivial, as you can partition the Latin squares in $n-1$ sets, defined by the value of $L(2,1)$ (or any specific coordinates not on the first line) : this forms a partition and two Latin squares in the same set cannot be orthogonal, hence $\chi(G_n) \leq n-1$. Apr 14, 2020 at 6:13