Reminder : 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 ] × [ n ] → S, i.e., an n × n array with elements in S, such that each element of S appears exactly once in each row and each column. For example,Latin square 1, 2, 3 3, 1, 23, 1, 2Let L 1 and L 2 be two Latin squares over the ground sets S 2 respectively. They are called orthogonal if for every ( x 1 , x 2 ) ∈ S 1 × S 2 there exists a unique ( i , j ) ∈ [ n ] × [ n ] such that L 2 ( i , j ) = x 2 . For example, the following are two orthogonal Latin squares of order 3.1, 2, 3 2, 3, 13, 1, 2 3, 1, 21, 2, 1 1, 2, 3It 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.Graph : 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 , … , 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 × K n ! As I'm mainly interested in the chromatic number of my graph, and we know that χ ( H n ) ≤ min { χ ( G n ) ; n ! }, I will study only G n For instance 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 χ ( G n ) ≥ n − 1I 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 χ ( G n ) ≤ Δ + 1Can G n contains an induce k-cycle with k&gt;3 (i.e. chordless cycle)?Can it be conjectured thatConjecture : for any n, G n is the disjoint union of complete subgraphs (of different sizes).Edit After some simple Brute force and some additional reading, I can tell that G 4 is made of 2 disjoint K 3 and 18 isolated vertices, for a total of 24 Latin squares up to permutations. G 5 is made of 36 disjoint K 4 and 1200 isolated vertices, for a total of 1344 Latin squares up to permutation.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 were mutually orthogonal. So G 6 is made of only isolated 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&gt;6, if n is not of the form 2p for a prime p ≥ 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

Question

Reminder : 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  ]  ×  [  n  ]  →  S, i.e., an   n  ×  n array with elements in S, such that each element of S appears exactly once in each row and each column. For example,Latin square 1, 2, 3 3, 1, 23, 1, 2Let       L    1   and       L    2   be two Latin squares over the ground sets       S    2   respectively. They are called orthogonal if for every   (      x    1    ,      x    2    )  ∈      S    1    ×      S    2   there exists a unique   (  i  ,  j  )  ∈  [  n  ]  ×  [  n  ] such that       L    2    (  i  ,  j  )  =      x    2  . For example, the following are two orthogonal Latin squares of order 3.1, 2, 3     2, 3, 13, 1, 2     3, 1, 21, 2, 1     1, 2, 3It 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.Graph : I&#039;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  ,  …  ,  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    ×      K          n      !      As I&#039;m mainly interested in the chromatic number of my graph, and we know that   χ  (      H    n    )  ≤  min  {  χ  (      G    n    )  ;  n  !  }, I will study only       G    n  For instance       G    3    =      K    2  I know that :It&#039;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   χ  (      G    n    )  ≥  n  −  1I 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   χ  (      G    n    )  ≤  Δ  +  1Can       G    n   contains an induce k-cycle with k&amp;gt;3 (i.e. chordless cycle)?Can it be conjectured thatConjecture : for any n,       G    n   is the disjoint union of complete subgraphs (of different sizes).Edit After some simple Brute force and some additional reading, I can tell that      G    4   is made of 2 disjoint       K    3   and 18 isolated vertices, for a total of 24 Latin squares up to permutations.      G    5   is made of 36 disjoint       K    4   and 1200 isolated vertices, for a total of 1344 Latin squares up to permutation.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 were mutually orthogonal. So       G    6   is made of only isolated 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 &quot;Monogamous Latin Square by Danziger, Wanless and Webb, available on Wanless website here. The authors show that for all n&amp;gt;6, if n is not of the form 2p for a prime   p  ≥  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

Kristin Myers · Accepted Answer

at the MathOverflow posting of this question, Brendan McKay addresses the conjecture by using referencing examples of   10  ×  10 latin squares with more than one mate however the pair aren&#039;t individuals of a at the same time orthogonal triple.There&#039;s more from the heavily-studied   10  ×  10 case relevant to your questions. The maximum degree in the graph is likely unbounded. Here&#039;s a relevant excerpt from pp327-328 of Latin Squares and Their Applications by Keedwell and Dénes (2nd ed., North Holland, 2015).&quot;[Parker in 1962 and 1963] discovered that   10  ×  10 latin squares with orthogonal mates are not, in fact, particularly scarce and he also showed that there exist squares with a large number of alternative orthogonal mates. His most striking result concerns the square displayed in Figure 13.2.1 which has 5504 transversals and an estimated one million alternative orthogonal mates (that is, sets of 10 disjoint transversals). However, Parker was able to show by a partly theoretical argument that no two of these alternative orthogonal mates are themselves orthogonal and so, much to his own disappointment, he was not able to obtain a triad of mutually orthogonal   10  ×  10 latin squares. The existence or non-existence of such triads remains an open question.&quot;In fact, that particular square has 12,265,168 orthogonal mates (Maenhaut and Wanless, J. Combin. Des. 12 (2004) 12-34).

Answered question

Answer & Explanation

New Questions in High school statistics