Luminary Research Archive
Luminary Research ArchiveIndependent scholarship
Luminary Portal
PublicEdition 3

A linear query lower bound for graph-isomorphism testing at maximum degree three

Scott Schubr

Original PDF · First-page preview

Loading original first page…

Abstract

For every sufficiently large even N, this paper exhibits existentially a known connected simple 3-regular N-vertex target whose randomized two-sided isomorphism testing requires Ω(N) incidence queries at proximity 1/175, even with connected cubic inputs promised. It also gives maximum-degree-three fixed targets at every sufficiently large integer order. These results sharpen Dror’s maximum-degree-thirteen construction and reach the minimum maximum-degree threshold: degree two admits size-independent query bounds. The proof retains Dror’s sparse-code and adaptive indistinguishability framework. A compact 17n-vertex encoding admits the arbitrary-bijection bound dist_H(b, Im A) ≤ (3/4) dist_iso(G_b, G_0): one intact variable cycle anchors an assignment bit, and unmatched source edges pay for unanchored variables and defective rows. Bounded paired triangle expansions handle every even order without a multiplicative distance loss. The older capped completion family has normalized distance at most 4/429 < 0.01 on every input.

Read the full paper in the original PDF.

Edition files

Available editions

  1. Edition 7 · 2026-11-02 · public
  2. Edition 6 · 2026-10-27 · public
  3. Edition 5 · 2026-10-27 · public
  4. Edition 4 · 2026-10-24 · public
  5. Edition 3 · 2026-10-24 · public
  6. Edition 2 · 2026-10-24 · public
  7. Edition 1 · 2026-10-24 · public

Research details

Subjects
Mathematics · Computer Science & Software Systems · Combinatorics and Graph Theory · Algorithms and Complexity
Keywords
graph isomorphism testing, bounded-degree graphs, incidence queries, connected cubic graphs, subcubic graphs, query complexity, robust decoding
Manuscript date
2026-10-23
Reader reuse
No additional permission granted

Scope

The results concern classical randomized two-sided incidence-query testing against existential known targets, with unrestricted target preprocessing and computation. The connected simple 3-regular theorem holds for every sufficiently large even order at proximity 1/175, with connected simple cubic inputs promised. The all-order maximum-degree-three theorem retains proximity 10⁻⁶. The earlier capped encoding has a universal distance upper bound of 4/429 < 0.01; that obstruction applies to this family rather than all possible encodings.

Disclosures

AI-assisted tools supported research exploration, literature review, manuscript preparation and internal verification. The author retains responsibility for the work.

Reproduction

The seventeen-member package contains the complete twelve-page manuscript, self-contained LaTeX source and bibliography, six standard-library Python verification programs, six public result files, reader instructions, citation metadata and a sixteen-entry checksum manifest. With Python 3.10 or later, run verify_encoding.py, verify_combinatorics.py, verify_cubic.py, verify_core_transfer.py, verify_connectivity.py and verify_proximity.py with distinct --output filenames, then repeat under python -O. Keep adjacent files together and follow README.md for comparison rules; the combinatorial optimized receipt differs only in its optimized Boolean. Build main.tex with Tectonic or two pdflatex runs. Finite checks corroborate the encoding, exact combinatorics, cubic components, core transfer, connectivity, compact proximity construction and selected negative controls; the asymptotic lower bounds follow from the analytic proofs.

References and related resources

  1. A. Dror, A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree Model, ECCC TR26-268 (2026).
  2. O. Goldreich and L. Tauber, Testing in the Bounded-Degree Graph Model with Degree Bound Two, LNCS 15700 (2025), 373–382.
  3. O. Goldreich, Testing Isomorphism in the Bounded-Degree Graph Model, LNCS 15700 (2025), 293–323.
  4. O. Goldreich and L. Tauber, On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model, LNCS 15700 (2025), 324–337.
  5. J.-Y. Cai, M. Fürer and N. Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), 389–410.
  6. V. Arvind, J. Köbler, S. Kuhnert and Y. Vasudev, Approximate Graph Isomorphism, MFCS 2012, LNCS 7464, 100–111.
  7. R. O’Donnell, J. Wright, C. Wu and Y. Zhou, Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs, SODA 2014, 1659–1677.
  8. Y. Chen, J. Flum and M. Liu, Some remarks on the uncolored versions of the original CFI-graphs, arXiv:2507.01459 (2025).
  9. M. Goetze, P. Jungeblut and T. Ueckerdt, Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs, Algorithmica 88 (2026), article 11.