# Coloring in Combinatorial Design Generalizing Latin Square

I have a question about a combinatorial design very similar to a Latin Square, which is arising out of an open problem in graph theory. The design is an $$n \times n$$ matrix whose entries we want to assign colors from $$\lbrace 1, 2, \dots, n \rbrace$$. A (symmetric) Latin Square is subject to the following constraints:

1) The matrix should be symmetric.

2) No row or column contains the same color more than once.

In my problem, we will want a symmetric $$n \times n$$ matrix, but we will allow some of the matrix entries to be identified into symmetric blocks. In other words, suppose there is an equivalence relation $$\mathcal{A}$$ on the coordinates $$(a_{i,j})$$ which satisfies the property that if $$A \in \mathcal{A}$$ and $$a_{i,j} \in A$$, then $$a_{j,i} \in A$$. The problem I am curious about is, if given an $$n$$ and an arbitrary such $$\mathcal{A}$$, is there an $$n \times n$$ matrix satisfying the following constraints:

1) The matrix is symmetric.

2) If $$a, b \in A$$ for some $$A \in \mathcal{A}$$, then the entries are assigned the same color, and

3) If two coordinates $$a, b$$ are in the same row or column as one another and they are the same color, then there is an $$A \in \mathcal{A}$$ such that $$a, b \in A$$.

In other words, it's a symmetric Latin Square 'up to equivalence by $$\mathcal{A}$$.'

Have these objects been studied before (with or without the symmetry condition), or are there any equivalent formulations? I expect that it is possible to construct such a design. I can only prove it in very special cases, though (e.g. where each row or column only 'intersects' at most one non-trivial equivalence class).

• I would expect this is a fundamental sort of question in matroid theory, but I barely even know the definition of a matroid. If someone has a matroid expert friend... – John Samples Jul 11 '19 at 2:54
• So you might want to replace the tag [matrix-theory] by [matroid-theory]. 😊 – Wolfgang Jul 11 '19 at 5:07
• Sincerely, I do not feel this being matroid-related, of course I may be wrong. – Fedor Petrov Jul 11 '19 at 6:52

Hope I didn't misunderstand the question, but isn't this a counterexample (different letters correspond to different equivalence classes):

AAB
ACD
BDC


Each pair of classes have representatives in a common row/column, hence at least four colours are needed.

• Maybe it's me who got a misunderstanding of the question, but what's wrong with using four colors? – M. Winter Sep 13 '19 at 18:31
• Yes, it's a counterexample. But don't worry, my actual problem is still open. There are some extra niceties in my situation, which I'm going to rewrite into the OP. Check back in a bit. Honestly I totally forgot about this post haha – John Samples Sep 15 '19 at 0:20

If I understand correctly, these are symmetric frequency squares. Quoting from a random reference on the topic:

An $$F(n;\lambda_1,\ldots,\lambda_m)$$ frequency square is an $$n \times n$$ array consisting of the numbers $$1,2,\ldots,m$$ with the property that for each $$i = 1,\ldots,m$$, the number $$i$$ occurs exactly $$\lambda_i$$ times in each row and in each column.
Dénes and Mullen, Enumeration formulas for latin and frequency squares, Disc. Math., 1993

Some Latin squares have the property that they're symbol-isotopic to their transpose. I.e., for some Latin squares $$L$$, you can permute the symbols of $$L^T$$ to obtain $$L$$. We can identify symbols to obtain the desired frequency squares.

To my knowledge, the only paper that talks about such Latin squares is: Mendis and Wanless, Autoparatopisms of Quasigroups and Latin Squares, J. Combin. Des., 2016. (There may be others that I'm unaware of.) Theorem 4.7 in this paper gives necessary and sufficient conditions for the existence of these Latin squares.

• It seems like a relaxed version of what I have in mind; I'm going to rewrite this question to be clearer now that some people have responded and just go ahead and give away why I am asking (it's equivalent to an Erdos problem). It is a relaxed version because just getting the frequency of each color/number is not enough, we will have a particular pattern within the array. – John Samples Sep 15 '19 at 0:12
• Maybe it would be best to give an example of a matrix you're referring to? – Rebecca J. Stones Sep 15 '19 at 0:25