Triangle-free strongly regular graphs form a fascinating byway of combinatorics. These are regular graphs of valency k on v vertices, which contain no triangles, and have the property that any two non-adjacent vertices have μ common neighbours. The numbers (v,k,μ) are the parameters of the graph. (For general strongly regular graphs, instead of the triangle-free condition, we require that two adjacent vertices have λ common neighbours; so a triangle-free s.r.g. is just a s.r.g. with λ=0.)
The complete bipartite graph Kk,k is an example, with v=2k and μ=k. For the rest of this post, I exclude this trivial case.
Some restrictions on the parameters are known, but there are infinitely many “feasible” parameter sets which satisfy all known necessary conditions. However, only finitely many examples are known, with parameters (5,2,1), (10,3,1), (16,5,2), (50,7,1), (56,10,2), (77,16,4) and (100,22,6). The big question is: Are there any more?
Probably anyone who thought about these graphs made the following construction. Let X be a triangle-free s.r.g. Choose a vertex * of X, and define an incidence structure, or block design, as follows: the points are the neighbours of *, the blocks are the non-neighbours, and a point and a block are incident if they are adjacent in the graph X. This structure has the following properties:
- There are k points;
- Any block is incident with μ points;
- Any two points are incident with μ−1 blocks;
- Any block is disjoint from at least k−μ other blocks.
The first two properties are clear. For the third, triangle-freeness shows that any two points are non-adjacent, and so have μ common neighbours, one of which is *; the rest are blocks. For the fourth property, each block is adjacent to μ points and so to k−μ blocks; and triangle-freeness shows that adjacent blocks are disjoint.
The existence of a design with these properties does not guarantee the existence of a triangle-free s.r.g., of course. But it enables us to reconstruct the entire graph apart from the edges between blocks. In “nice” cases, the number of blocks disjoint from any given block is exactly k−μ, so the whole graph is forced.
For μ=1, the design is completely trivial; but other information is available in this case. These are the Moore graphs of diameter 2, attaining the upper bound v ≤ k2+1 for the number of vertices of a graph of diameter 2 and valency k. Hoffman and Singleton showed that k is 2, 3, 7 or 57. The graphs in the first three cases exist and are unique; the existence of the Moore graph of valency 57 is a famous open problem.
For μ=2, things are more interesting, since there are infinitely many feasible parameter sets: k must be one more than the square of a number not divisible by 4. The blocks of the design consist of all the 2-element subsets of the point set. For k=5, there are exactly 5−2=3 blocks disjoint from a given one, so the construction is forced; the graph constructed this way is the Clebsch graph, and is strongly regular. Note that the edges of the complete graph on 16 vertices can be partitioned into three copies of the Clebsch graph, showing that the Ramsey number R(3,3,3) is at least 17; in fact, equality holds.
The situation for μ>2 is even more interesting, since only two examples are known. For μ=4 and k=16, we use the “affine symplectic design” whose blocks are the cosets of 2-dimensional singular subspaces for a symplectic form on a 4-dimensional vector space over the field of 2 elements. There are 15 blocks disjoint from a given one, including three parallel to it; we make two blocks adjacent if they are disjoint but not parallel. For μ=6, k=22, we have the famous Witt design, which has exactly 16 blocks disjoint from a given one; so blocks are adjacent if and only if they are disjoint. (The automorphism group of the Witt design is the group M22:2, containing the simple sporadic Mathieu group M22 as a subgroup of index 2.)
The last construction gives a strongly regular graph on 1+22+77=100 vertices, whose automorphism group contains the sporadic Higman–Sims simple group as a subgroup of index 2. This was perhaps the most painless construction of any sporadic simple group, having been performed in one day in Oxford in 1967. Marshall Hall had just announced the construction of the Hall–Janko group as a rank 3 permutation group on 100 points, so Higman and Sims decided to find another such group. They came up with the construction just described. It is clear that the stabiliser of * is the automorphism group of the Witt design, which is M22:2; all Higman and Sims had to do was to show that the automorphism group of the graph moves the vertex * (which they did by showing that starting from a different vertex gives again the Witt design), and that the automorphism group contains an odd permutation (an element of M22:2 outside M22 has this property). The rest is easy!
Until recently, the graph was always referred to as the Higman–Sims graph. But in 2002, Jajcayová and Jajcay, in the Bulletin of the Institute of Combinatorics and its Applications, drew attention to the fact that the graph had been constructed by Dale Mesner in his 1956 PhD thesis. Mesner died in 2009. In the most recent issue of the Bull. ICA, Klin and Woldar have a paper describing how Mesner constructed the graph, with some interesting side comments.
Mesner was at a serious disadantage compared to Higman and Sims: he was unaware of Witt’s construction and uniqueness proof for his design, published in 1938. Mesner was a statistician working in experimental design; Higman and Sims were group theorists, and very familiar with Witt’s work because of its connection with the Mathieu groups. So Mesner had to construct the design himself, which he did without the assistance of a computer. Indeed, in his thesis, he showed that there were at most four possible designs, and that one of them produced a strongly regular graph; later he completed the uniqueness proof for the graph by showing that a design with the required properties is also unique. In this he was also at a disadvantage since the fact that the design is a 3-design (that is, any three points lie in a constant number of blocks, namely just one) simplifies the argument considerably; but t-designs were only invented by Dan Hughes in the 1960s. (Hughes says that it was Donald Higman who suggested the terminology.)
Against that, Higman and Sims had a little more to do, since they had to show that the automorphism group is vertex-transitive and almost simple.
Perhaps it is unlikely that we will stop calling the graph the Higman–Sims graph and refer to it as the Mesner graph; but Klin and Woldar hope that at least we will recognise Mesner’s priority in its discovery.
The article gives some very interesting insights into Mesner’s mathematics and personality. For example, he wrote,
The author conjectured that the design did not exist in this case, undertook an empirical search in hopes of proving its nonexistence, and in the course of the search inadvertently discovered it
This method of proof is reminiscent of Bhaskhara whose 1150 A.D. treatise on mathematics presented a sketch of a particularly lucid construction for the Pythagorean theorem, accompanied by the brief written proof, “Behold!”.
My own career was strongly affected by this business. Arriving in Oxford as a student in 1968, the year after the discovery there of the Higman–Sims group, I began working on groups in which the point stabiliser acts multiply transitively on some orbit. This led me to the design interpretation sketched above, a theorem on the extension of symmetric 2-designs to 3-designs (which appeared as “Cameron’s Theorem” in the book on design theory by Hughes and Piper), and the re-discovery of Mesner’s feasible “negative Latin square” parameters, v=g2(g+3)2, k=g(g2+3g+1), μ=g(g+1), which for g=1 gives the Clebsch graph, and for g=2 the Mesner (or Higman–Sims) graph.
Although I never met Dale Mesner, Donald Higman was the external examiner of my DPhil thesis, and Charles Sims also visited Oxford while I was a student (and I generalised one of his unpublished theorems about paired subconstituents in transitive permutation groups).