Skip to content
Preprint

Less is Moore

Oct 2026 · 0 citations · 14 references
Computer Science Mathematics

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

View source

Similar papers

Preprint Nov 2026

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, remov...

A. Sadhu · 1 citation
Preprint Nov 2026

A King for Almost Everyone

A tournament is an orientation of a complete graph. A vertex $v$ controls a vertex $u\neq v$ if there is a directed path of length at most two from $v$ to $u$, and a $\delta$-king is one that controls at least $\delta(n-1)$ vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sh...

Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande · 0 citations
Preprint Nov 2026

Online packing of the three largest trees

For every $n\ge4$, arbitrary trees of orders $n,n-1,n-2$ can be packed into $K_n$ online, in decreasing order of size: each tree must be embedded before the next is revealed, and earlier embeddings cannot be changed. This strengthens the classical three-tree packing theorem of Hobbs, Bourgeois and Kasiraj (1987). In pa...

Maciej Cisiński · 0 citations
Preprint Oct 2026

The Value of Steiner Hubs in Two-Hop Distance Labeling

Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying arbitrary real values. On no family is the value of that freedom known. We determine it on $\ell_1$ products of betweenness-fre...

Si-Chen Wang · 0 citations
Preprint Nov 2026

Circular flows and bisections of random regular graphs

For every fixed odd $d\ge5$, we prove that the circular flow number of a uniformly random simple $d$-regular graph is asymptotically almost surely less than $2+4/(d-1)-\varepsilon_d$ for an explicit constant $\varepsilon_d>0$. At degree five the upper bound is $3-1/24006$. At degree seven it is $21/8$, answering a ques...

A. Jafari · 0 citations
Preprint Oct 2026

Resolving Two Open Problems of Planar $B_k$-CPG Recognition: $k=0,1$

A $k$-bend path is a non-self-intersecting polyline that lies on a grid and consists of at most $k+1$ axis-parallel line segments. A $B_k$-CPG graph is a graph whose vertices can be represented by pairwise interiorly disjoint $k$-bend paths on a grid such that two vertices are adjacent if and only if the corresponding...

Bin-Jie Sun, Shou-Jun Xu, Yu Yang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.