Luminary Research Archive
Luminary Research ArchiveIndependent scholarship
Luminary Portal
PublicEdition 1

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 N, this paper exhibits existentially a known simple N-vertex graph of maximum degree at most three for which randomized two-sided isomorphism testing in the incidence-query model requires Ω(N) queries at an absolute positive proximity parameter. The result sharpens Dror’s maximum-degree-thirteen construction and reaches the minimum maximum-degree threshold, since degree two admits size-independent query bounds. The proof retains Dror’s sparse binary-code and adaptive indistinguishability framework and supplies a constant-size subcubic encoding with a one-bit incidence oracle. An arbitrary-bijection distance bound follows from local recognition of variable and parity components and partial decoding outside edge defects. The proximity parameter may be fixed at 10⁻⁶. The target is a simple graph of maximum degree at most three.

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, subcubic graphs, query complexity, robust decoding
Manuscript date
2026-10-23
Reader reuse
No additional permission granted

Scope

The theorem concerns classical randomized two-sided incidence-query testing against an existential known target, for all sufficiently large graph sizes, with unrestricted target preprocessing and computation. Sparse-code, CFI, approximate-isomorphism and robust-decoding ancestry is explicitly credited.

Disclosures

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

Reproduction

The nine-member package contains the complete seven-page PDF, self-contained LaTeX source and bibliography, two standard-library Python verifiers, their public results, reader instructions, citation metadata and a checksum manifest. With Python 3.10 or later, run verify_encoding.py and verify_combinatorics.py with --output filenames distinct from the supplied receipts, then repeat under python -O. Follow README.md for comparison rules: combinatorial receipts differ only in the optimized Boolean. Build main.tex with Tectonic or two pdflatex runs. Finite checks corroborate the encoding, local decoding and exact combinatorics; the all-size lower bound follows from the analytic proof.

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