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
1 · Permanent link

You are reading a preserved edition. Read the current edition (v3).

Read / download PDF Publication filesCite this edition

Overview

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⁻⁶. Targets need not be regular or connected.

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

Scope of the work

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. It does not establish an efficient uniform construction, a fixed regular or connected target theorem, a quantum lower bound, or computational graph-isomorphism hardness. Sparse-code, CFI, approximate-isomorphism and robust-decoding ancestry is explicitly credited; worldwide priority remains qualified.

Reproduction notes

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.

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

A stable scholarly record

Cite this edition

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

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

Loading discussion…