Return to Answer

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 can't be "all $j$ subsets of an $N$-set" in a non-trivial way. Perhaps it could be something less symmetric.

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.

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$.)

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.

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 can't be "all $j$ subsets of an $N$-set" in a non-trivial way. Perhaps it could be something less symmetric.

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 Peterson 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$.)

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 Peterson 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.

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$.)

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.