8
$\begingroup$

In a comment on a blog post from 2009 about the hypothetical Moore graph(s) of degree 57 and girth 5, Gordon Royle offered the following observation (reproduced here in full for the sake of preservation):

Here’s some blue-sky numerology (I think Chris Godsil told me this originally, but I can’t remember).

Spectral theory tells us that an independent set in this hypothetical Moore graph can have at most 400 vertices, leaving 2850 left over.

These are magic numbers though, because 400 is the number of points in PG(3,7) and 2850 is the number of lines in PG(3,7). So perhaps we can construct a Moore graph with an independent set of size 400 by using the points of PG(3,7) as the independent set and the lines of PG(3,7) as the remaining vertices. The natural incidence between points and lines in PG(3,7) yields exactly the required number of edges between the two parts.

So this leaves us just the challenge of deciding adjacency among the 2850 “line-type” vertices.

If we take one of the 400 “point-type” vertices, then it has 57 line-type vertices as neighbours, and each of those has a further 49 line-type vertices as its neighbours. All 57.50 = 2850 of these must be distinct and so this configuration is a collection of 57 spreads of PG(3,7) that collectively use all the lines, or in other words a packing of PG(3,7).

So all we need to do is find 400 packings of PG(3,7) that fit together properly!!

My question is: have there been any results from (or even serious attempts at) taking this approach? Do we even know if this approach is compatible with the known properties that such a Moore graph must posess, if it were to exist (e.g.: automorphism group must have order $\leq$ 375 [1])?

[1] Macaj, Martin, and Jozef Širán. "Search for properties of the missing Moore graph." Linear Algebra and its Applications 432 (2010): 2381-2398.

$\endgroup$
7
$\begingroup$

Adding to the allure of this deadly siren song is the fact that there are constructions of this sort for the Moore graph of degree $3$ (the Petersen Graph with 10 vertices and independence number $4$) and the Moore Graph of degree $7$ ( the Hoffman-Singleton graph with $50$ points and independence number $15$.) The only other possible degrees are $2$ (a pentagon) and perhaps $57.$

WARNING: BEWARE!

PG(3,1) would be a tetrahedron with $4$ points and $6$ lines and $4$ faces (planes). One can label (in two essentially different ways) the lines with pairs from the set $\{a,b,c,d\}$ so that two lines are coincident exactly if their labels have intersection of size $1$. There are $8$ ways to have a (maximal) clique of three pairwise intersecting lines. Of these cliques, $4$ correspond to the triples and $4$ correspond to the elements. Depending on how the labeling was done, one kind is the points and the other is the planes. Either way, we have the three spreads (rulings) $ab|cd$, $ac|bd$ and $ad|bc.$

For the Petersen graph, use lines and points of PG(1,3) to label $10$ vertices. Make an edge for incident point-line pairs and also for label disjoint (i.e common ruling) line-line pairs. That is the graph.

PG(3,2) has $2^3+2^2+2+1=15$ points and $35$ lines with each point on $7$ lines. There are also $15$ Fano planes. It turns out that the lines of PG(3,2) can be labeled (in various ways) with the $35$ triples from the set $S=\{a,b,c,d,e,f\}$ in such a way that two lines are coincident precisely when the labels have one element in common. Let me avoid, or at least delay, the issues of describing how to do this and finding the points and planes of PG(3,2) from the structure of the line graph.

For the Hoffman-Singleton Graph, use lines and points of PG(2,3) to label $50$ vertices. Make an edge for incident point-line pairs and also for label disjoint line-line pairs That is the graph! Consider a line-type vertex and the four line-type vertices it is joined to in the graph. The corresponding lines constitute a spread in PG(2,3).

Let me get back to PG(3,2). Consider the various ways to select seven pairwise intersecting lines, no three sharing a common element in the label. Any such septad gives $S$ the structure of a Fano plane. There are $6$ ways to do this using a particular line so $\frac{35\cdot 6}7=30$ in all. The obvious action of $S_7$ is transitive while $A_7$ splits these into two orbits of size $15.$ Depending on how the labeling was done, one kind is the points and the other is the planes.

I intentionally tried to make the two constructions sound as similar as possible. Both, being amazing, have much more structure and have combinatorial objects contained and containing them. Also there is a great deal of symmetry so the graphs have huge automorphism groups. A possible Moore graph of degree $57$ would have a small automorphism group.

If there is a Moore graph of degree $57$ (which seems doubtful) and it has a similar construction, the labeling of the $2850$ lines of PG(3,7) can't be "all $j$ subsets of an $N$-set" in a non-trivial way. Perhaps it could be something less symmetric.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Isn't Petersen spelled with an 'e' (actually 3 'e's) rather than an 'o'? $\endgroup$ – Gordon Royle Feb 14 '19 at 6:05
1
$\begingroup$

According to [1], as of 2015, there were no known packings (aka parallelisms) of PG(3,7) despite it being known via Beutelspacher's theorem [2] that at least one such packing must exist. Given that we don't even have one explicit packing of PG(3,7), I must conclude that it is very unlikely that there have been substantial efforts at pursuing this line of investigation in the context of Moore graphs.

  1. S. Zhelezova, "On point-cyclic parallelisms of PG(3,7)". Mathematics and Education in Mathematics (2015) 101 – 105.

  2. Beutelspacher, Albrecht. "On parallelisms in finite projective spaces." Geometriae Dedicata 3.1 (1974): 35-40.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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