THE FOLD / RESPAWN / THE CONTINUE / THE MOORE BOUND
THE MOORE BOUND
a shape that may or may not exist
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Fix a degree d and a diameter k. Counting outward from any vertex bounds the graph: at most 1 + d·∑(d−1)i vertices can exist. A graph that meets that bound is called a Moore graph, and hitting it forces extraordinary symmetry — which is why almost none exist. For diameter 2 the only possibilities are d=3 (the Petersen graph, 10 vertices), d=7 (Hoffman–Singleton, 50) and d=57, which would need 3,250 vertices. Nobody has built it. Nobody has ruled it out. It has been open since 1960.
LIT verified live: the bound gives 10, 50 and 3,250 for d = 3, 7, 57 at diameter 2, and 22 for d=3 at diameter 3; the Petersen graph is constructed here as the Kneser graph K(5,2) and confirmed to have 10 vertices, be 3-regular, have diameter 2 and girth 5 — meeting the bound exactly.
LIT verified live: the bound gives 10, 50 and 3,250 for d = 3, 7, 57 at diameter 2, and 22 for d=3 at diameter 3; the Petersen graph is constructed here as the Kneser graph K(5,2) and confirmed to have 10 vertices, be 3-regular, have diameter 2 and girth 5 — meeting the bound exactly.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE CONTINUE: a search that has been running for over sixty years and has neither succeeded nor terminated.
AVAN (AI) built the Petersen graph rather than asserting its properties, because the bound is only interesting if something actually attains it. Constructing it as the Kneser graph K(5,2) — vertices are the 2-element subsets of a 5-set, joined when disjoint — and then measuring degree, diameter and girth by breadth-first search is a genuine check that the definition produces the object. The classification is a different matter and is cited, not verified: that d = 3, 7 and possibly 57 are the only diameter-2 cases is due to Damerell and independently Bannai–Ito in 1973, and nothing on this page establishes it. What is on the page is the bound, one graph that meets it, and an open question.
AVAN (AI) built the Petersen graph rather than asserting its properties, because the bound is only interesting if something actually attains it. Constructing it as the Kneser graph K(5,2) — vertices are the 2-element subsets of a 5-set, joined when disjoint — and then measuring degree, diameter and girth by breadth-first search is a genuine check that the definition produces the object. The classification is a different matter and is cited, not verified: that d = 3, 7 and possibly 57 are the only diameter-2 cases is due to Damerell and independently Bannai–Ito in 1973, and nothing on this page establishes it. What is on the page is the bound, one graph that meets it, and an open question.
3 ONE DIMENSION
Counting outward. Each ring is (d−1) times the last, and that is the whole bound.
4 TWO DIMENSIONS · INTERACTIVE
Walk out from any vertex of the Petersen graph and watch it close exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the Petersen graph, as symmetric as a graph can be made.
AVAN’s addition (the inverse-companion): the forward reading is “Moore graphs are rare.” The inverse is that the bound is a counting argument and the rarity is an algebraic consequence, and those are not the same subject. Nothing about counting outward suggests scarcity — the bound is satisfiable in arithmetic for every d. What kills the candidates is that attaining it forces the adjacency matrix to have a very particular spectrum, and integrality of those eigenvalues then permits only d = 3, 7, 57. Read backwards, the missing graphs are not missing for combinatorial reasons at all; they are excluded by a condition on the square roots of integers, which is why the last case has resisted for sixty years.
LIT the bound gives 10, 50 and 3,250 for d = 3, 7, 57 at diameter 2, and 22 for d=3 at diameter 3; the Petersen graph is CONSTRUCTED here as the Kneser graph K(5,2) and confirmed to have 10 vertices, be 3-regular, have diameter 2 and girth 5 — meeting the bound exactly
FIG The Petersen graph is built rather than asserted, because a bound is only interesting if something attains it: constructing it as K(5,2) and measuring degree, diameter and girth by breadth-first search checks that the definition produces the object. The CLASSIFICATION is a different matter and is cited, NOT verified — that d = 3, 7 and possibly 57 are the only diameter-2 cases is due to Damerell and independently Bannai-Ito in 1973, and nothing here establishes it.
FIG The Petersen graph is built rather than asserted, because a bound is only interesting if something attains it: constructing it as K(5,2) and measuring degree, diameter and girth by breadth-first search checks that the definition produces the object. The CLASSIFICATION is a different matter and is cited, NOT verified — that d = 3, 7 and possibly 57 are the only diameter-2 cases is due to Damerell and independently Bannai-Ito in 1973, and nothing here establishes it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CONTINUE · David Lee Wise (ROOT0), with AVAN