Instant TravelLuminary Oddities — Enter the Portal
Research Archive

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
Primary subject
Computer Science & Software Systems
Subject subfields
Algorithms and Complexity · Combinatorics and Graph Theory
Paper type
Research Article
Manuscript stage
Preprint
Manuscript
Archived
Edition
3 · Permanent link
Read / download PDF Publication filesCite this edition

Overview

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. The literal proximity-0.01 question remains open.

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

Scope of the work

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. Efficient uniform construction, quantum lower bounds and computational graph-isomorphism hardness are not asserted. The literal proximity-0.01 problem remains unresolved.

Reproduction notes

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.

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

A stable scholarly record

Cite this edition

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

BibTeX
@techreport{luminary_linear_query_lower_bound_graph_isomorphism_testing_maximum_degree_three_v3,
  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 3},
  url = {https://research.luminaryoddities.com/linear-query-lower-bound-graph-isomorphism-testing-maximum-degree-three/v/3}
}

Loading discussion…