The Shrikhande graph

The logo of the Interational Conference on Recent Trends in Graph Theory and Combinatorics, held in Cochin, in Kerala, in mid-August 2010, was a particular 16-vertex graph known as the Shrikhande graph. Its discoverer, the Indian mathematician S. S. Shrikhande, was also one of the “Euler spoilers”, along with R. C. Bose and E. T. Parker. The two topics are not unconnected, so I thought that, by way of celebrating this excellent conference that I attended in August, I would explain the connection.

Consider first the following graph, sometimes denoted by L₂(4). The vertices of the graph form a 4×4 array, and two vertices are joined by an edge if and only if they are in the same row or column. The graph has 16 vertices; each vertex has 6 neighbours (three in the same row, and three in the same column); and any two vertices have 2 common neighbours. The last statement involves considering cases. A typical pair of vertices in the same row are (1,1) and (1,2); their common neighbours are (1,3) and (1,4). For two vertices in the same column, the argument is similar. Two vertices in different rows and different columns look like (1,1) and (2,2), and have common neighbours (1,2) and (2,1).

Shrikhande showed that L₂(4) is not the only graph with these properties. There is one other, now called the Shrikhande graph. As a first hint of its connection with the Euler problem, here is a concise way to define these graphs.

A Latin square of order n is a n×n array with entries from the symbol set {1,2,…,n}, such that each symbol occurs once in each row and once in each column. Now it is not hard to show that, up to permutations of the rows, columns and symbols, there are only two Latin squares of order 4:

1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3

Now, given a Latin square, we define the corresponding Latin square graph as follows: the vertices are the n² cells of the array; two vertices are joined if the two cells lie in the same row, or in the same column, or contain the same entry.

If you construct the complementary graphs (interchanging edges and non-edges) of the two Latin squares of order 4 shown, you will find that the first is the graph L₂(4); the second one is the Shrikhande graph.

The Euler conjecture and its demise

Two Latin squares of the same order are said to be orthogonal if, for each pair (k,l) of symbols, there is a unique cell (i,j) which contains k in the first square and l in the second.

If we replace the symbols {1,…,n} by letters from two different alphabets, say the Latin and Greek alphabets, the requirement is that, if the two squares are superimposed, then every combination of a Latin and a Greek letter occurs exactly once. For this reason, a pair of orthogonal Latin squares is often called a Graeco-Latin square; the term Latin square is a back-formation, from the case where there is only one alphabet.

These terms were invented by Euler. He defined and studied Graeco-Latin squares in order to give a new construction of magic squares. (A magic square is an n×n square with entries 1,…,n² such that each row, column, and diagonal has the same sum. The study of magic squares began in China a very long time ago, and was taken up by Arab and Byzantine mathematicians in the middle ages. As usual in those days, they were doing applied mathematics: magic squares were regarded as talismans.)

Euler asked,

Six different regiments have six officers, each one holding a different rank. Can these 36 officers be arranged in a square formation on the parade ground so that each row and column contains one officer of each rank and one from each regiment?

This asks whether orthogonal Latin squares of order 6 exist (the ranks and the regiments are the symbols in the two squares). He thought the answer was “no”:

Euler knew how to construct orthogonal Latin squares of all orders greater than 1 except for those congruent to 2 (mod 4). He conjectured that they did not exist for orders congruent to 2 (mod 4). This is trivial for order 2, and was proved by Tarry by exhaustive case analysis for order 6 in 1900. There matters rested until 1960, when Bose, Shrikhande and Parker showed that it is false for all other values: a pair of orthogonal Latin squares of order n exist for all values of n except for n=2 and n=6.

The programme book for the Cochin conference contains short biographies of the Euler spoilers by Mohan Shrikhande.

Mutually orthogonal Latin squares

I have to begin with a couple of definitions. First, a collection of Latin squares is said to be mutually orthogonal if any two of its members are orthogonal. The phrase “mutually orthogonal Latin squares” is abbreviated MOLS. (Acronyms ending with S are dangerous: I have seen “MOL” used as a singular word!) A set of MOLS of order n can have at most n–1 members. For suppose we have a set of r MOLS. By symbol permutations we can assume that each square has entry 1 in the top left corner. There are (n–1)r further ones; they cannot occur in the first row or column (so there are only (n–1)² positions where they can occur), and no two can occur in the same position. So (n–1)r ≤ (n–1)².

A set of n–1 MOLS of order n is called complete. Complete sets of MOLS are very important in combinatorics: the existence of such a set is equivalent to that of a projective or affine plane of order n. The question of for which n they exist is extremely hard. The current state of our knowledge is: a complete set of MOLS

• exists if n is a prime power;
• does not exist if n is congruent to 1 or 2 mod 4 and n is not a sum of two squares;
• does not exist if n=10 (this is the result of a huge computation by Clement Lam and his collaborators).

Stronger results than the falsity of Euler’s conjecture have been proved; it is known that the maximum size of a set of MOLS of order n is bounded below by a slowly-growing function of n (a small positive power).

The connection

A strongly regular graph with parameters (N,k,λ,μ) is a graph with the following properties:

• there are N vertices;
• each vertex has k neighbours;
• two adjacent vertices have λ common neighbours;
• two non-adjacent vertices have μ common neighbours.

Thus L₂(4) and the Shrikhande graph are both strongly regular with parameters (16,6,2,2).

Much more generally, suppose that we have a set S of s–2 MOLS. Form a graph, much as we did for L₂(4), by taking the n² cells as vertices; two vertices are adjacent if and only if they are in the same row, or the same column, or contain the same symbol in one of the Latin squares in S. Some counting shows that this graph (which is called a Latin square graph and denoted by L_s(n)), is strongly regular, with parameters

N=n², k=s(n–1), λ=(n–2)+(s–1)(s–2), μ=s(s–1).

Now we call an arbitrary strongly regular graph with these parameters a pseudo Latin square graph, and denote it by pseudo-L_s(n). Thus the Shrikhande graph is a pseudo-L₂(4).

For completeness, we define an L₁(n) to be the disjoint union of n complete graphs of size n, and an L₀(n) to be n² isolated vertices.

The complement of a strongly regular graph is again a strongly regular graph, whose parameters can be expressed in terms of those of the original graph. In particular, the complement of a pseudo-L_s(n) is a pseudo-L_t(n), where t=n+1-s.

If the complement of an L_s(n) is an L_t(n), with this relation, then the MOLS together form a complete set.

Now we can return to Shrikhande. What he really proved was the following:

A pseudo-L₂(n) is a L₂(n) if n is not equal to 4; for n=4, there is a unique exception (the graph we now call the Shrikhande graph).

This has the following consequence:

If n≠4, then a set of n–3 MOLS of order n can be extended (in a unique way to a complete set of MOLS.

The exclusion is necessary since, as we saw, there are two different Latin squares of order 4; one, but not the other, can be extended to a complete set of 3 MOLS.

The theorem was substantially extended by Bruck in 1963, who showed the following:

There is a function f (with f(s) roughly s⁴) such that, if n≥f(s), then a pseudo-L_s(n) is a L_s(n).

This implies that, under the same hypotheses, a set of n–s–1 MOLS of order n can be (uniquely) extended to a complete set.

Unfortunately the gap between the maximum number of MOLS of order n known to exist, and the minimum number needed to apply Bruck’s theorem, is vast!

Bruck’s theorem was extended to the class of “geometric” strongly regular graphs by Bose (in a paper immediately following Bruck’s in the Pacific Journal of Mathematics) and then to arbitrary strongly regular graphs by Neumaier; but that is another story…