Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
These are the Moore graphs, right? So 7 exists and 57 is unknown. –  Harry Altman Oct 28 '10 at 1:50
    
Sorry, I mean Moore graphs of girth 5. –  Harry Altman Oct 28 '10 at 1:55
3  
Indeed, the existence of a Moore graph of degree 57 is one of the most mysterious and exciting open problems in combinatorics. –  Gil Kalai Oct 28 '10 at 18:43
3  
I would love to know why exactly it is such a mysterious and exciting open problem! –  Mariano Suárez-Alvarez Jan 30 '12 at 0:18
add comment

2 Answers

up vote 22 down vote accepted

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.

share|improve this answer
    
See also C D Godsil, Problems in algebraic combinatorics, Electron J Combin 2 (1995) Feature 1, MR 96b:05051. –  Gerry Myerson Oct 28 '10 at 2:10
    
Thank you very much! –  David Speyer Oct 28 '10 at 2:10
11  
Shouldn't we arrange our lectures so we teach spectral techniques on Halloween? –  Gerry Myerson Oct 28 '10 at 5:25
5  
Then spectral sequences should come at Christmas (for the three that visit Ebenezer Scrooge). –  Allen Knutson Oct 28 '10 at 18:26
3  
See math.harvard.edu/~elkies/Misc/hsgraph.pdf for an outline of an elementary proof of the uniqueness of the Hoffman-Singleton graph. –  Noam D. Elkies Jan 30 '12 at 1:39
show 2 more comments

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?

share|improve this answer
2  
$A_5$ has order 60. –  Gerry Myerson Oct 28 '10 at 5:23
4  
The automorphism group of the Petersen graph is isomorphic to the symmetric group on 5 elements. (There is a nice exercise in chapter one of Meier's book "Groups, Graphs, and Trees" which outlines a proof that the automorphisms freely permute the five 4-vertex induced subgraphs which are totally disconnected.) –  Robert Bell Oct 28 '10 at 11:51
2  
Aschbacher only proved the automorphism group could not be a rank-3 group, ie, the graph on 3250 vertices could not be distance transitive. G. Higman proved that it could not be vertex transitive. Martin Mačaj and Jozef Širáň recently showed that order of the group is at most 375. –  Chris Godsil Oct 28 '10 at 18:18
    
Aha, thanks for the correction, I'll put it in. –  Aaron Meyerowitz Oct 28 '10 at 21:32
2  
Possibly the most natural way to see the action of $S_5$ is to identify the $10$ vertices with $5 \choose 2$ pairs and say two pairs are adjacent iff they're disjoint. (In other words, the Petersen graph is the complement of the "triangle graph $T_5$".) –  Noam D. Elkies Jan 30 '12 at 3:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.