23
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ These are the Moore graphs, right? So 7 exists and 57 is unknown. $\endgroup$
    – Harry Altman
    Commented Oct 28, 2010 at 1:50
  • $\begingroup$ Sorry, I mean Moore graphs of girth 5. $\endgroup$
    – Harry Altman
    Commented Oct 28, 2010 at 1:55
  • 4
    $\begingroup$ Indeed, the existence of a Moore graph of degree 57 is one of the most mysterious and exciting open problems in combinatorics. $\endgroup$
    – Gil Kalai
    Commented Oct 28, 2010 at 18:43
  • 5
    $\begingroup$ I would love to know why exactly it is such a mysterious and exciting open problem! $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jan 30, 2012 at 0:18

2 Answers 2

Reset to default
26
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ See also C D Godsil, Problems in algebraic combinatorics, Electron J Combin 2 (1995) Feature 1, MR 96b:05051. $\endgroup$
    – Gerry Myerson
    Commented Oct 28, 2010 at 2:10
  • 11
    $\begingroup$ Shouldn't we arrange our lectures so we teach spectral techniques on Halloween? $\endgroup$
    – Gerry Myerson
    Commented Oct 28, 2010 at 5:25
  • 5
    $\begingroup$ Then spectral sequences should come at Christmas (for the three that visit Ebenezer Scrooge). $\endgroup$
    – Allen Knutson
    Commented Oct 28, 2010 at 18:26
  • $\begingroup$ @Gerry-Myerson, or perhaps talk about the Pentagram map near Halloween? math.usf.edu/research/colloquia = October 29 2010 Geometry, algebra, and dynamics of the pentagram map, by speaker Sergei Tabachnikov, Penn State... $\endgroup$
    – sleepless in beantown
    Commented Nov 7, 2010 at 4:47
  • 4
    $\begingroup$ See math.harvard.edu/~elkies/Misc/hsgraph.pdf for an outline of an elementary proof of the uniqueness of the Hoffman-Singleton graph. $\endgroup$
    – Noam D. Elkies
    Commented Jan 30, 2012 at 1:39
12
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Robert Bell
    Commented Oct 28, 2010 at 11:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Godsil
    Commented Oct 28, 2010 at 18:18
  • $\begingroup$ Aha, thanks for the correction, I'll put it in. $\endgroup$
    – Aaron Meyerowitz
    Commented Oct 28, 2010 at 21:32
  • 3
    $\begingroup$ 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$".) $\endgroup$
    – Noam D. Elkies
    Commented Jan 30, 2012 at 3:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .