Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices? - MathOverflow

Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

2010-10-28T01:42:09Z

The following problem is homework of a sort -- but homework I can't do!

The following problem is in Problem 1.F in Van Lint and Wilson:

Let $G$ be a graph where every vertex has degree $d$. Suppose that $G$ has no loops, multiple edges, $3$-cycles or $4$-cycles. Then $G$ has at least $d^2+1$ vertices. When can equality occur?

I assigned the lower bound early on in my graph theory course. Solutions for $d=2$ and $d=3$ are easy to find. Then, last week, when I covered eigenvalue methods, I had people use them to show that there were no solutions for $d=4$, $5$, $6$, $8$, $9$ or $10$. (Problem 2 here.) I can go beyond this and show that the only possible values are $d \in \{ 2,3,7,57 \}$ , and I wrote this up in a handout for my students.

Does anyone know if the last two exist? I'd like to tell my class the complete story.

Answer by Hsien-Chih Chang for Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

2010-10-28T02:02:12Z

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at most

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

Answer by Aaron Meyerowitz for Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

2010-10-28T03:45:53Z

Additional random facts.

The Peterson Graph can be obtained by identifying the antipodal points of a dodecahedron and it has $S_5$ as its automorphism group (order 120 of course).

There are a number of geometric constructions of the Hoffman-Singleton Graph (the 25 points and 25 non-vertical lines of an affine plane over $Z_5$ are used in one , the 15 points and 35 lines of projective 3-space over $Z_2$ in another). The automorphism group has order 252000.

A Moore graph of degree 57, if it exists, ~~would have a trivial automorphism group:~~ would have to have a small automorphism group. edit See the comment below from Chris Godsil

Aschbacher, M. "The Non-Existence of Rank Three Permutation Group of Degree 3250 and Subdegree 57." J. Algebra 19, 538-540, 1971.

Here is a good reference from 2010: Search for properties of the missing Moore graph which shows among other things that if such a graph exists then it has automorphism group of order at most 375.

later Since we have new interest I'll add some beautiful well known facts.

The triangle graph $T_5$ is the line graph of $K_5$ and is regular of degree 6 with 10 vertices. So $S_5$ acts on it and that is the full automorphism group. As mentioned by N. Elkies, the Peterson graph is the complement of $T_5$. $T_5$ has five maximal cliques $K_4$ corresponding to the 5 vertices. These become the five totally disconnected 4-vertex induced sub-graphs (independent sets) mentioned by R. Bell. If we fix one such independent 4-set, connect one new vertex with each of the six pairs and then connect each of these to the one pair disjoint from it, we get the Peterson Graph. So this is the points and edges of a tetrahedron.
In a Moore graph of order 7 the largest independent sets have 15 vertices. The incidence between these and the other 35 is the same as that between the points and blocks of a certain resolvable Steiner triple system and (equivalently) that between the 15 points and 35 lines of PG(3,2). These descriptions leave some edges unspecified, but:
Consider the 35 triples from ${a,b,c,d,e,f,g}$ as labels for 35 vertices and connect each to the four with labels disjoint from its own. There are 30 heptads being choices of seven triples no two disjoint (so forming a Fano plane). $S_7$ is transitive on these but $A_7$ has two orbits of size 15. If we use one such orbit to label 15 more vertices and make the obvious connections, we get the Moore graph of order 7.
The Peterson graph has a nice description in terms of the 4 points and 6 edges of a tetrahedron or PG(3,1) if we abuse notation. The Moore graph of order 7 has a nice description in terms of the 15 points and 35 lines of PG(3,2). Now, PG(3,7) has 400 points and 2850 lines and if there is a Moore graph of order 57 (warning! warning! Many would conjecture that there is none!) then it has 400+2850 vertices of which at most 400 could be independent... The fact that a large automorphism group has been ruled out makes this an unpromising approach, but who knows?