Equitable partitions of Latin square graphs

On our recent trip to Shanghai, Rosemary Bailey and I met Sergey Goryainov, who gave a talk about some joint work with his supervisor Alexander Gavrilyuk at the International Workshop on Bannai–Ito Theory in Hangzhou. I mentioned it in my write-up and promised more to follow. The follow-up is here: Rosemary and I got to work on the problem and together the four of us have proved a generalisation.

I have spoken about the result at the Combinatorics Study Group in Queen Mary and at the St Andrews Research Day. A paper containing the complete proof of the theorem is now on the arXiv.

Equitable partitions

Let Γ be a finite graph; I will always assume it to be connected and regular with valency k. Let Ω be its vertex set.

A partition Π = {S₁,…,S_r} of Ω is said to be equitable if there is a r×r matrix M (the quotient matrix of the equitable partition) such that a vertex in S_i has exactly m_ij neighbours in S_j.

Equitable partitions of graphs include a large number of structures of interest in finite geometry and combinatorics. Here are a few examples.

• Let G be a group of automorphisms of Γ. Then the orbits of G on the vertex set of Γ form an equitable partition.
• Consider the distance partition of Γ with respect to a vertex v: this is the partition Π whose ith part is the set of vertices at distance i from v, for i=0,…,d (where d is the diameter of Γ. These partitions are all equitable with the same matrix if and only if Γ is distance-regular: this is equivalent to the usual definition of a distance-regular graph.
• Many important structures in finite geometry, including ovoids, spreads, and “Cameron–Liebler line classes”, fit into this framework.

We call a subset S of Ω perfect if the partition into S and its complement is equitable.

Theorem: The spectrum of the quotient matrix of an equitable partition is contained in the spectrum of the adjacency matrix A(Γ) of Γ.

To see this, let V be the real vector space of real functions on Ω, and let v_i be the characteristic function of S_i. Then from the definition we get

v_iA(Γ) = ∑m_jiv_j,

so the subspace spanned by the vectors v_i is invariant under A(Γ), and the matrix of the restriction relative to the given basis is the quotient matrix of the equitable partition.

In particular, in the case of a distance-regular graph, the quotient matrix M of the distance partition has each eigenvalue of A(Γ) with multiplicity 1.

Since Γ is regular and connected, its valency k is a simple eigenvalue of A(Γ). Also, the matrix M of the equivariant partition has all row sums equal to k; so k is an eigenvalue of M, called the principal eigenvalue.

If S is a perfect set such that the matrix of the partition {S,Ω\S} has eigenvalues k and μ, then we call S a μ-perfect set.

Here I am concerned with equitable partitions with just one non-principal eigenvalue. These of course include all such partitions with just two parts. In general, the partition Π has all non-principal eigenvalues equal to μ if and only if the characteristic vectors of its parts all lie in the sum of the eigenspaces with eigenvalues k and μ of A(Γ). From this fact, we get the following results, which reduce the problem of their classification to that of the minimal μ-perfect sets:

Proposition: Let Π = {S₁,…,S_r} be a partition of the vertex set of the connected regular graph Γ.

• If Π is equitable with all non-principal eigenvalues μ then each set S_i is μ-perfect.
• Conversely, if all but one of the S_i are μ-perfect, then Π is equitable with all non-principal eigenvalues μ.

We call such partitions Π μ-equitable.

Latin square graphs

A Latin square L is a n×n array with entries from the set {1,…,n}, such that each letter occurs once in each row and once in each column.

Latin squares are important in combinatorics, since they are highly regular structures (giving rise to strongly regular graphs, as we will see) but exist in great profusion (the number of Latin squares of order n grows faster than the exponential of n²).

Given a Latin square L, the corresponding Latin square graph Γ has as vertices the n² cells of L, two cells being adjacent if they lie in the same row or the same column or contain the same letter.

It is well known that this graph is a strongly regular graph (a distance-regular graph with diameter 2), which has valency 3(n−1), and whose other eigenvalues are n−3 (with multiplicity 3(n−1)) and −3 (with multiplicity (n−1)(n−2)).

Proposition: In a Latin square graph, the set of cells in any row (or in any column, or containing any letter) is (n−3)-perfect.

For a cell in a row is joined to n−1 other cells in that row and 2(n−1) cells outside; while a cell outside a row is joined to two cells in the row (one in the same column, and one with the same letter) and 3n−5 cells outside. So the partition is equitable, with matrix having eigenvalues 3(n−1) and n−3. It follows that any partition, each of whose parts is a union of rows (or columns, or letters), is equitable, with all non-trivial eigenvalues equal to n−3.

Are there any others?

At the International Workshop on Bannai–Ito Theory in Hangzhou, China, in November 2017, Sergey Goryainov talked about the following result that he and Alexander Gavrilyuk had proved:

Theorem: Let L be the Cayley table of an elementary abelian 2-group G of order n. Then a minimal (n−3)-perfect set in the Latin square graph is a row, a column, a letter, or the set of n²/4 cells corresponding to a subgroup of G of index 2.

Rosemary and I decided to have a go at generalising this result … Eventually the gang of four came up with a complete solution.

The main theorem

We found a couple more constructions.

Corner sets: Let L be the Cayley table of the cyclic group of order n, which we regard as being the set of integers modulo n. A typical corner set looks like this:

A fairly simple calculation shows that a corner set is (n−3)-perfect.

We will also call a set obtained from a corner set as above by permuting rows, columns or letters a corner set.

Inflation: Let L₀ be a Latin square of order s. Construct an n×n array, where n = st, by replacing each entry of L₀ by a Latin square of order t, where the squares which replace a given letter all use the same alphabet of size t, and the alphabets associated with different letters of L₀ are pairwise disjoint. The resulting array is a Latin square L of order n, called an inflation of L₀.

A short calculation shows that if S₀ is a set of cells of L₀ which is (s−3)-perfect, then the set of |S₀|t² cells of L in the corresponding subsquares is (n−3)-perfect. We call this set an inflation of S₀.

Again, we use the same term for any square obtained by permuting rows, columns and letters.

In particular, in the unique Latin square of order 2, any single cell is a corner set; inflating this we see that, in a Latin square of even order n, any subsquare of order n/2 is an inflation of a corner set, and so is (n−3)-perfect.

Now we can state the main theorem:

Theorem: A minimal (n−3)-perfect subset of a Latin square graph from a square of order n is a row, a column, a letter, or an inflation of a corner set in a cyclic square.

The proof of this is quite complicated and I will not attempt even a sketch here. Read it on the arXiv if you are interested!

Going further?

The other non-principal eigenvalue of a Latin square graph is −3. Can we say anything about −3-perfect sets? Such a set S has the property that it meets any row, column or letter in a constant number s of cells, and its cardinality is sn.

In particular, with s = 1, such set is a transversal, a set containing one cell from each row, column or letter. One of the oldest conjectures about Latin squares is Ryser’s conjecture, asserting that any Latin square of odd order has a transversal. Many squares of even order do too, but some do not (for example, the Cayley table of the cyclic group). The conjecture is still open despite a lot of work, so characterising such sets is unlikely to be achieved soon!

We see also that, if an equitable partition Π has all non-principal eigenvalues −3, then all its parts satisfy the above condition, so that rows, columns, letters, and parts of Π form an orthogonal array of strength 2. In particular, if our square has an orthogonal mate, then the letters of this mate form such a partition.

There is a partition with parts of sizes 7, 14 and 28 of a Latin square of order 7 derived from the Fano plane.

If we consider partitions where both non-principal eigenvalues occur, there is much more freedom, and probably no hope of a classification. To mention just two examples:

• The distance partition of the graph with respect to any cell. (As noted earlier, the non-principal eigenvalues each occur with multiplicity 1.)
• The partition into t×t subsquares associated with a t-fold inflation of a Latin square of order s. (Both non-principal eigenvalues occur if and only if s > 2.)