The Sylvester graph
There is a distance-transitive graph on 36 vertices with valency 5 known as the Sylvester graph.
The graph was first constructed by Norman Biggs and his co-authors in their work on small distance-transitive graphs. I asked Norman about the name. He referred me to Coxeter’s paper “Twelve points in PG(5,3) with 95040 self-transformations” in Proc. Royal Soc. A 247 (1958), 279–293. Coxeter gives a table of duads and synthemes, from which the graph can be constructed. According to Norman, this might have been taken from H. F. Baker’s monograph A locus with 25920 linear self-transformations, in Cambridge Math. Tracts no. 39, 1946. (I have not seen this book.) Norman said in his email to me,
Nowhere can I find the name Sylvester graph, and I think we can be fairly sure that Sylvester himself never considered such a graph.
However, the graph is most easily constructed using Sylvester’s notions of duads and synthemes. I described these in one of the posts on the symmetric group here; you may wish to refresh your memory by looking at that post before continuing.
The Sylvester graph lives on a 6×6 square grid; the vertices are those of the grid, and the five neighbours of a vertex v are in different rows and columns from v and from one another. Two vertices in the same row or column of the grid are thus at distance greater than 2; in fact they are at distance 3.
The construction is as follows. The rows are indexed by a set A of six points, and the columns by the set B of six synthematic totals on A (in Sylvester’s terminology; in other language, these are the six 1-factorisations of the complete graph on A.) One important property is that two synthematic totals share a unique syntheme (or 1-factor). Now the adjacency rule is that the point (a,b) is joined to the point (a’,b’) if and only if the pair {a,a’} of points is a duad (an edge) in the syntheme shared by the totals b and b’.
The Sylvester graph lives inside the Hoffman–Singleton graph, as follows. Add fourteen new vertices: the elements of A and B, and two new symbols α and β. The new edges are:
- each vertex (a,b) of the Sylvester graph is joined to a and to b;
- all vertices in A are joined to α, and all vertices in B are joined to β
- α and β are joined.
You can find the Sylvester graph (including a picture and a number of links) here, on Robert Bailey’s webpage DistanceRegular.org.
Designs from the Sylvester graph
Consider the block design whose points are the 36 vertices in the Sylvester graph and whose blocks are the 36 closed neighbourhoods (each consisting of a vertex and its five neighbours). Each block contains six points, one in each row of the grid, and one in each column. Two points lie together in at most two blocks: two points in the same row or column lie in no common blocks, two points with are joined in the graph lie in two common blocks (since the graph has no triangles), and two non-adjacent points in different rows and columns lie in one common block, since they have one common neighbour in the graph.
We can add twelve further blocks, the six rows and the six columns of the grid. In the resulting block design, two points are contained in either 1 or 2 common blocks, with six-sevenths of pairs in one common block.
An affine plane of order n is a block design with n2 points, and n(n+1) blocks, each containing n points, so that each pair of points is contained in a unique block. Examples are known for all prime powers n, and for no other values. In particular, it is known that there is no affine plane of order n.
However, if we take the design with 36 points and 42 blocks, consisting of the 36 closed neighbourhoods in the Sylvester graph and the six columns of the array, we have the right number of points and blocks and the right cardinalities of blocks; 5/7 of the point pairs are contained in unique blocks, and the other 2/7 in either 0 or 2 blocks (with equally many of each).
This design admits the symmetric group S6, fixing the rows and columns of the grid setwise.
Is this any use? Of course, not if you require an affine plane. However, there are various statistical measures of “optimality” of block designs, which allow comparisons among (real or hypothetical) designs with given numbers of points, blocks, and points per block. See here for explanation of these concepts. In particular, the value of the A-optimality criterion (which measures the average variance of estimators of differences between pairs of treatments – smaller variance = better design = larger value of the A-criterion) for the nonexistent affine plane would be 0.857, whereas the design just constructed realises the value 0.851, and so is scarcely inferior.
The design with 48 blocks is resolvable, that is, the blocks can be partitioned into 8 sets of size 6, each of which partitions the set of points. (Take the rows and the columns as two of these sets. Then choose to use either rows or columns, it makes no difference. Using rows, the six blocks of the Sylvester design consisting of closed neighbourhoods of points in a given row form a resolution class, and these six classes use all blocks of the design.)
So other designs can be built by deleting some of the resolution classes. Presumably, some of these will be good designs as well.
Time permitting, Rosemary and I will work out some of the details for these designs in the near future.
Peter Cameron's Blog 
I happened upon the Sylvester graph in my research recently. I was looking at Gallai graphs of strongly regular graphs. The Gallai graph of a graph G has the edges of G as its vertices, two being adjacent if they share a vertex but are not in a triangle together. If G is the categorical (direct) product of K_6 with itself, then the Gallai graph of G has a maximum independent set (meeting the Delsarte bound) whose elements correspond to edges of G that form a copy of the Sylvester graph. Any maximum independent set of the Gallai graph of this G will correspond to a 5-regular spanning subgraph of G whose distance 1 or 2 graph is also a subgraph of G, and the Sylvester graph is the least common occurring such subgraph (720 times out of 12,911,040 total). The most common is a disjoint union of 6-cliques (1,128,960 occurrences, which correspond to the 6-colorings of the complement of G).
Interesting! Thanks for this.
My first encounter with the Sylvester graph (though I didn’t know then that it was called that, Norman Biggs had probably named it only a little earlier) was in 1972, back in the days when we didn’t have CFSG and so theorems about multiply-transitive groups were still worth proving. I considered a group G with two different 3-transitive permutation representations so that the stabiliser of a point in each set acts in the same way on both sets. I showed that such a group must be either affine over GF(2) or the symmetric group S_6. In the latter case, I built the graph, and extended it to a Moore graph of diameter 2 and valency n+1, (where n is the degree) from which one concludes that n=6.
The design which you constructed it by Sylvester graph can be used in authentication code construction, as an important area of cryptography. Dear Prof. CameronIs, is the Sylvester graph Cayley?
I think the answer is no. This would require a subgroup of order 36 in S_6.2 which acts transitively on the vertices of the Sylvester graph. I tried a few possibilities and couldn’t find one that works. But it shouldn’t be too hard a job, since such a subgroup would lie inside the normaliser of a Sylow 3-subgroup of S_6.2. Maybe I missed something…
Indeed, GAP assures me that there is no transitive subgroup of order 36 in the automorphism group of the Sylvester graph.
Here is another occurrence of the Sylvester graph. In my recent work with Marina Anagnostopoulou-Merkouri and Rosemary Bailey, we generalised the theorem of Krasner and Kaloujnine on wreath products. If G is a transitive but imprimitive permutation group, then G is embeddable in H wr K, where H is the stabiliser of a block of imprimitivity acting on its points, and K the group induced on the set of blocks by G. We have extended this theorem to “generalised wreath products” — I won’t attempt to define these here but they include direct product (in product action) as well as wreath product. But our first attempt failed, because of S_6 acting on the vertices of the Sylvester graph. There are two block systems forming a 6 by 6 grid. The stabiliser of a block is S_5 and acts on it as PGL(2,5). But S_6 is not embeddable in the direct product of two copies of PGL(2,5). So, for the general case, we had to modify the definition of the ingredients, the transitive groups that are fed into the generalised wreath product to obtain a group embedding G.
The paper is on the arXiv, number 2409.10461.