Less is Moore
Abstract
A Moore graph simultaneously asks for two things that normally pull in opposite directions: every vertex should have many neighbors, while every pair of vertices should remain close. For diameter two and degree k, the Moore bound is k2+1, and equality forces a remarkably rigid graph: it is strongly regular with parameters (k2+1,k,0,1). Hoffman and Singleton showed that such a graph can exist only for k=2,3,7, and possibly 57. The degree-57 case on 3,250 vertices remains open. This paper is not an attempt to settle that open problem. Instead, we ask a more algorithmic question: How efficiently can the defining Moore structure itself be searched exactly? We begin from a human-developed exhaustive search based on the radius-two Moore tree. Leaves fall into k groups of size k−1, and the edges between every pair of such groups form a perfect matching - a permutation. For efficiency, a partial construction is abandoned immediately when it creates a triangle or quadrangle. We then describe a sequence of exact algorithm-engineering improvements developed through a human-guided AI process and accepted only after mathematical checking and controlled regression tests. The main steps are reversible short-cycle forbid counters, bit-parallel domains, minimum-remaining-value branching, singleton propagation, matching-based AllDifferent filtering, balanced replayable parallel frontiers, residual-symmetry orbit pruning, and canonical deduplication of frontier states. On the principal k=9 benchmark, stronger symmetry cuts wall time from 47.6 to 17.9 seconds on a six-core laptop setup. Further parallelization speedup is reported separately; on a 16-core/32-thread machine, median wall time is reduced to 5.28 seconds. Degrees 10 and 57 are used as stress tests, and a five-minute degree-57 run uses only 161 MiB peak resident memory, showing that state size is modest.
Related
- Moore-Postnikov supcation of simplicial sets and applications in simplicial algebras
- Antitonicity property of the Moore-Penrose inverse for selfadjoint operators
- Graphs of Moore-Penrose inverse of matrices possessing the treeangle property
- Left properness of Moore flows
- Additive results of the dual Moore--Penrose generalized inverse with an application to rigid-body motion estimation
BibTeX
@misc{wagner2026less,
title = {{Less is Moore}},
author = {Paul Stankovski Wagner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04815},
eprint = {2610.04815},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04815},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Less is Moore
AU - Paul Stankovski Wagner
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04815
UR - https://arxiv.org/abs/2610.04815
AB - A Moore graph simultaneously asks for two things that normally pull in opposite directions: every vertex should have many neighbors, while every pair of vertices should remain close. For diameter two and degree k, the Moore bound is k^2+1, and equality forces a remarkably rigid graph: it is strongly regular with parameters (k^2+1,k,0,1). Hoffman and Singleton showed that such a graph can exist only for k=2,3,7, and possibly 57. The degree-57 case on 3,250 vertices remains open. This paper is not an attempt to settle that open problem. Instead, we ask a more algorithmic question: How efficiently can the defining Moore structure itself be searched exactly? We begin from a human-developed exhaustive search based on the radius-two Moore tree. Leaves fall into k groups of size k−1, and the edges between every pair of such groups form a perfect matching - a permutation. For efficiency, a partial construction is abandoned immediately when it creates a triangle or quadrangle. We then describe a sequence of exact algorithm-engineering improvements developed through a human-guided AI process and accepted only after mathematical checking and controlled regression tests. The main steps are reversible short-cycle forbid counters, bit-parallel domains, minimum-remaining-value branching, singleton propagation, matching-based AllDifferent filtering, balanced replayable parallel frontiers, residual-symmetry orbit pruning, and canonical deduplication of frontier states. On the principal k=9 benchmark, stronger symmetry cuts wall time from 47.6 to 17.9 seconds on a six-core laptop setup. Further parallelization speedup is reported separately; on a 16-core/32-thread machine, median wall time is reduced to 5.28 seconds. Degrees 10 and 57 are used as stress tests, and a five-minute degree-57 run uses only 161 MiB peak resident memory, showing that state size is modest.
ER -