Dyadic Saturation in Cubic Vertex-Transitive Graphs: A Complete PSV Census Theorem up to 1280 and a Mechanism Taxonomy
We study the Erdos-Gyárfás conjecture through a dyadic lens on the class of connected cubic vertex-transitive graphs. For a graph G we dene the dyadic ground length ℓ∗(G) = min{2k ≥4 : C2k (G) ̸= ∅} and the associated valuation v2(G) = log2(ℓ∗(G))−1, setting v2(G) = ∞ when no power-of-two cycle exists. Using the complete Poto£nikSpigaVerret (PSV) census of all cubic vertex-transitive graphs of order at most 1280 (111,360 graphs), we obtain a computational theorem: every census graph contains a cycle of length 4, 8, 16, or 32 (equivalently, v2(G) ≤4 throughout the census window), and no instance with dyadic silence beyond 32 occurs. The elite set v2 = 4 consists of exactly 100 graphs and decomposes cleanly into three disjoint structural routes: Triangle-Crystal (TF = 1) with 53 graphs, Bipartite-Voltage (bipartite) with 30 graphs, and a genuinely non-bipartite, non-crystalline Route 3 with 17 graphs. An odd-girth analysis of the Route-3 elite reveals three species of frustrated symmetry ranging from pentagonal (g = 5) through quasi-bipartite (g= 6, odd girth up to 21) to high-girth extremes (g≥9). We present the route taxonomy, certify all counts and artifacts deterministically (no sampling), and formulate a corrected proof program beyond the census window: since cubic vertex-transitive graphs can have arbitrarily large girth, no constant dyadic lter length can hold order-free; the natural upgrade target is EGC-type dyadic existence together with quantitative control of dyadic depth growth via matching-lattice and quotient/cover methods.
Authors
- Jonas Gebendorfer
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-02-13
- DOI
- https://doi.org/10.5281/zenodo.18631619
- Primary Topic
- Theoretical and Computational Physics
- Type
- article
- Field-Weighted Citation Impact
- 0.00