Research Archive

Luminary Research ArchiveIndependent scholarship

Luminary Portal

Research Article · Preprint Computer Science & Software Systems

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

Scott Schubr

Luminary Oddities LLC

  • Computer Science & Software Systems
  • Algorithms and Complexity
  • Combinatorics and Graph Theory
Paper type
Research Article
Manuscript stage
Preprint
Manuscript
Archived
Edition
4 · Permanent link
Read / download PDF Publication filesCite this edition

Overview

Abstract

For every sufficiently large even N, we exhibit existentially a known connected simple 3-regular N-vertex target whose randomized two-sided isomorphism testing requires Ω(N) incidence queries at literal proximity 0.01, even with connected cubic inputs promised. This gives a negative answer to Goldreich’s Open Problem 4.1 in its stated distance normalization. We also retain maximum-degree-three fixed targets at every sufficiently large integer order, reaching the minimum maximum-degree threshold since degree two admits size-independent query bounds. We use Dror’s sparse-code and adaptive indistinguishability framework. A no-rung 16n-vertex parity encoding has the arbitrary-bijection estimate dist_H(b, Im A) ≤ (2/3) dist_iso(G_b, G_0). Adaptive coloring of imported target middle vertices, a joint defective-row budget, and median assignment rounding handle arbitrary mixing of graph roles. Bounded equivariant surgeries cover every even order with additive distance loss at most 322. An upper bound 4/429 < 0.01 for the older capped family explains why that completion method alone cannot reach the numerical endpoint.

Keywords graph isomorphism testing · bounded-degree graphs · incidence queries · connected cubic graphs · subcubic graphs · query complexity · robust decoding

Scope of the work

For every sufficiently large even N, an existentially selected known connected simple 3-regular target requires Ω(N) randomized classical two-sided incidence queries at literal proximity 1/100, even with connected simple cubic inputs promised. Target preprocessing and computation are unrestricted. Distance is minimum unordered-edge symmetric difference under arbitrary vertex bijections, normalized by 3N/2; deletions and insertions both count. The proof gives an unrestricted dist_H ≤ (2/3) dist_iso bound, a connected (3,9) sparse-matrix input, exact entropy gap and all-even padding with total additive loss 322. The original all-order maximum-degree-three theorem at 10⁻⁶ and the capped-family 4/429 obstruction are retained. The obstruction is specific to that capped family. No efficient uniform construction, quantum lower bound, computational GI hardness, expansion or bridgelessness claim is made. Internal checks are not external human refereeing.

Reproduction notes

The nineteen-member package contains the complete thirteen-page paper, editable self-contained LaTeX source and bibliography, seven standard-library Python verification programs, seven public result files, reader/build instructions, citation metadata and an eighteen-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, verify_proximity.py and verify_literal.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. The literal verifier checks 5,064 selected maps, including isolate/type mixing and adaptive middle/median charges, plus all 24 even padding residues through 15,360 graphs and 8,137,728 padding oracle answers. Production fault controls must reject. These finite checks support fragile mechanisms; the universal and asymptotic conclusions follow from the full analytic proof.

The manuscript

Read the paper

Open PDF

The complete manuscript, as published in this edition.

If the reader is unavailable on your device, open or download the PDF directly.

Author disclosures

AI-assisted tools supported research exploration, literature review, manuscript preparation and internal verification. The author retains responsibility for the work. Internal AI-assisted and computational checks are distinct from external human peer review.

References and related publications

  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; Open Problem 4.1.
  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.
  10. I. Adler, N. Köhler and P. Peng, On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing, SIAM J. Comput. 53(4) (2024), 825–883.
  11. K. Makarychev, R. Manokaran and M. Sviridenko, Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm, arXiv:1403.7721 (2014).

A stable scholarly record

Cite this edition

Scott Schubr. (2026). A linear query lower bound for graph-isomorphism testing at maximum degree three (Version 4). Luminary Research Archive. https://research.luminaryoddities.com/linear-query-lower-bound-graph-isomorphism-testing-maximum-degree-three/v/4

BibTeX
@techreport{luminary_linear_query_lower_bound_graph_isomorphism_testing_maximum_degree_three_v4,
  title = {A linear query lower bound for graph-isomorphism testing at maximum degree three},
  author = {Scott Schubr},
  year = {2026},
  institution = {Luminary Research Archive},
  type = {Research Article},
  note = {Version 4},
  url = {https://research.luminaryoddities.com/linear-query-lower-bound-graph-isomorphism-testing-maximum-degree-three/v/4}
}

Loading discussion…