pith. sign in

arxiv: 2605.28402 · v1 · pith:F7OFJOTMnew · submitted 2026-05-27 · 🧮 math.CO

On the Smallest Eigenvalues and Quantum Chromatic Numbers of Hamming Graphs and Generalizations

Yu Ning , Jack H. Koolen , Xiande Zhang This is my paper

Pith reviewed 2026-06-29 11:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords Hamming graphssmallest eigenvaluesquantum chromatic numberCayley graphsquaternary vectorsdistance-j graphsasymptotic bounds
0
0 comments X

The pith

Asymptotic lower bounds on smallest eigenvalues of Hamming graphs match known upper bounds on quantum chromatic numbers for quaternary Cayley graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the smallest eigenvalues of distance-j Hamming graphs in the regime where j is strictly less than half the length, the case left open by earlier complete determinations for larger j. It derives asymptotic lower bounds in the binary case and exactly determines the eigenvalue asymptotically for the natural generalization to Cayley graphs on quaternary vector spaces. These eigenvalue results are applied to produce lower bounds on the quantum chromatic numbers of the graphs. For the quaternary Cayley graphs the new lower bounds coincide with existing upper bounds.

Core claim

By deriving asymptotic lower bounds on the smallest eigenvalues of binary Hamming graphs for j less than half the length and exactly determining the eigenvalue for the quaternary Cayley graphs, the work obtains lower bounds on quantum chromatic numbers; in the quaternary case these lower bounds coincide with known upper bounds.

What carries the argument

The smallest eigenvalue of the adjacency matrix of the distance-j Hamming graph (or its quaternary Cayley generalization), used to bound the quantum chromatic number.

If this is right

  • The quantum chromatic numbers of the quaternary Cayley graphs are asymptotically determined.
  • Lower bounds on quantum chromatic numbers hold for binary Hamming graphs in the j < n/2 regime.
  • The eigenvalue analysis extends the earlier complete determination that covered only j at least half the length.
  • The matching of bounds holds specifically for the quaternary generalizations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same eigenvalue technique may produce matching bounds for quantum chromatic numbers on other families of distance-regular graphs.
  • Exact (non-asymptotic) values of the quantum chromatic number could be obtained by refining the eigenvalue estimates for finite n.
  • The results suggest that quantum chromatic number and classical chromatic number may differ by a constant factor in these graph families.

Load-bearing premise

The graphs obey the standard combinatorial definitions of distance-j Hamming graphs and quaternary Cayley graphs, and the analysis is restricted to the asymptotic regime with j strictly less than half the length.

What would settle it

A numerical computation of the smallest eigenvalue for a sequence of binary or quaternary graphs with growing length n and fixed ratio j/n < 1/2 that lies below the stated asymptotic lower bound would falsify the claim.

read the original abstract

The smallest eigenvalues of (distance-j) Hamming graphs with distance parameter j at least half the length were completely determined by Brouwer et al. (2018). In the present work, we address the complementary regime, namely distances j strictly less than half the length, and derive asymptotic lower bounds on the smallest eigenvalue of binary Hamming graphs. For certain natural generalizations, specifically Cayley graphs defined over quaternary vector spaces, we asymptotically determine the smallest eigenvalue as well. As an application, we obtain lower bounds on the quantum chromatic number of these graphs. In particular, for the aforementioned Cayley graphs over quaternary vectors, our lower bounds for the quantum chromatic number coincide with known upper bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper addresses the complementary regime to Brouwer et al. (2018) by deriving asymptotic lower bounds on the smallest eigenvalues of binary distance-j Hamming graphs for j strictly less than n/2. For Cayley graphs over quaternary vector spaces, it asymptotically determines the smallest eigenvalue exactly. These spectral results are applied to produce lower bounds on the quantum chromatic numbers of the graphs; for the quaternary Cayley graphs the lower bounds coincide with known upper bounds.

Significance. If the derivations are correct, the coincidence of bounds determines the quantum chromatic number (asymptotically) for the quaternary family, which is a concrete advance at the interface of spectral graph theory and quantum information. The work relies on standard eigenvalue techniques for distance-regular graphs and their Cayley generalizations in the stated regime, completing the picture left open by prior literature.

minor comments (1)
  1. The abstract refers to 'certain natural generalizations' without naming the precise Cayley graphs; a parenthetical clarification would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report accurately summarizes the contribution in the complementary regime to Brouwer et al. (2018) and the exact determination for the quaternary Cayley graphs.

Circularity Check

0 steps flagged

No significant circularity; extends external prior work on complementary regime

full rationale

The derivation addresses the j < n/2 regime left open by Brouwer et al. (2018), using standard spectral graph theory to obtain asymptotic lower bounds on the smallest eigenvalue of binary Hamming graphs and exact asymptotics for quaternary Cayley graphs. These bounds are then applied via the known eigenvalue-based lower bound on quantum chromatic number to match existing upper bounds. No step reduces by construction to a self-definition, fitted parameter renamed as prediction, or load-bearing self-citation chain; all load-bearing inputs are external literature or standard definitions. The result is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.1-grok · 5646 in / 909 out tokens · 42898 ms · 2026-06-29T11:51:14.143621+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 4 canonical work pages

  1. [1]

    Dual codes and their weight distribution. In F. J. MacWilliams and N. J. A. Sloane, editors, The Theory of Error-Correcting Codes, volume 16 ofNorth-Holland Mathematical Library, pages 125–154. Elsevier, 1977

    1977

  2. [2]

    Alon and B

    N. Alon and B. Sudakov. Bipartite subgraphs and the smallest eigenvalue.Combinatorics, Probability and Computing, 9(1):1–12, 2000

    2000

  3. [3]

    Bannai, E

    E. Bannai, E. Bannai, T. Ito, and R. Tanaka.Algebraic Combinatorics. De Gruyter, Berlin, Boston, 2021

    2021

  4. [4]

    Brassard, R

    G. Brassard, R. Cleve, and A. Tapp. Cost of exactly simulating quantum entanglement with classical communication.Physical Review Letters, 83(9):1874–1877, 1999

    1999

  5. [5]

    A. E. Brouwer, S. M. Cioab˘ a, F. Ihringer, and M. McGinnis. The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters. Journal of Combinatorial Theory, Series B, 133:88–121, 2018

    2018

  6. [6]

    A. E. Brouwer, A. M. Cohen, and A. Neumaier.Distance-Regular Graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics. Springer Berlin, Heidelberg, 1 edition, 1989

    1989

  7. [7]

    A. E. Brouwer and W. H. Haemers.Spectra of Graphs. Universitext. Springer New York, NY, New York, NY, 2012

    2012

  8. [8]

    Buhrman, R

    H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and com- putation. InProceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 63–68, New York, NY, USA, 1998. Association for Computing Machinery. 21

    1998

  9. [9]

    P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter. On the quantum chromatic number of a graph.Electronic Journal of Combinatorics, 14(1), 2007

    2007

  10. [10]

    X. Cao, K. Feng, H. Huang, Y. Yang, and Z. Zhang. On the quantum chromatic number of Hamming and generalized Hadamard graphs. arXiv:2510.14209, 2025

    work page arXiv 2025

  11. [11]

    X. Cao, K. Feng, and Y. Tan. Quantum chromatic numbers of some graphs in Hamming schemes. arXiv:2412.09904, 2024

    work page arXiv 2024

  12. [12]

    David, H

    A. David, H. Jun, K. Yosuke, and S. Yuuya. A quantum protocol to win the graph colouring game on all Hadamard graphs.IEICE Transactions on Fundamentals, E89-A(5):1378–1381, 2006

    2006

  13. [13]

    Diestel.Graph Theory

    R. Diestel.Graph Theory. Graduate Texts in Mathematics. Springer Berlin, Heidelberg, Berlin, Heidelberg, 6 edition, 2024

    2024

  14. [14]

    Dumer and O

    I. Dumer and O. Kapralova. Spherically punctured biorthogonal codes.IEEE Transactions on Information Theory, 59(9):6010–6017, 2013

    2013

  15. [15]

    Elphick and P

    C. Elphick and P. Wocjan. Spectral lower bounds for the quantum chromatic number of a graph.Journal of Combinatorial Theory, Series A, 168:338–347, 2019

    2019

  16. [16]

    F.-W. Fu, S. Ling, and C. Xing. New results on two hypercube coloring problems.Discrete Applied Mathematics, 161(18):2937–2945, 2013

    2013

  17. [17]

    C. D. Godsil and M. W. Newman. Coloring an orthogonality graph.SIAM Journal on Discrete Mathematics, 22(2):683–692, 2008

    2008

  18. [18]

    V. I. Levenshtein. Krawtchouk polynomials and universal bounds for codes and designs in Hamming-spaces.IEEE Transactions on Information Theory, 41(5):1303–1321, 1995

    1995

  19. [19]

    Lidl and H

    R. Lidl and H. Niederreiter.Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2 edition, 1996

    1996

  20. [20]

    T. Luo, Y. Ning, and X. Zhang. Quantum chromatic number of subgraphs of orthogonality graphs and the distance-2 Hamming graph. arXiv:2512.01195, 2025

    work page arXiv 2025

  21. [21]

    Manc´ ınska and D

    L. Manc´ ınska and D. E. Roberson. Oddities of quantum colorings.Baltic Journal on Modern Computing, 4(4):846–859, 2016

    2016

  22. [22]

    McNamara

    M. McNamara. The exact quantum chromatic number of Hadamard graphs. arXiv:2410.00042, 2024

    work page arXiv 2024

  23. [23]

    G. Nebe, E. M. Rains, and N. J. A. Sloane.Self-Dual Codes and Invariant Theory, volume 17 ofAlgorithms and Computation in Mathematics. Springer Berlin, Heidelberg, 1 edition, 2006

    2006

  24. [24]

    H. Robbins. A remark on Stirling’s formula.The American Mathematical Monthly, 62(1):26– 29, 1955

    1955

  25. [25]

    E. R. van Dam, J. H. Koolen, and H. Tanaka. Distance-regular graphs.The Electronic Journal of Combinatorics, Dynamic Surveys(DS22), 2016. 22

    2016

  26. [26]

    E. R. van Dam and R. Sotirov. New bounds for the max-k-cut and chromatic number of a graph.Linear Algebra and its Applications, 488:216–234, 2016

    2016

  27. [27]

    Wan.The MacWilliams Identity for Linear Codes over Galois Rings, pages 333–338

    Z.-X. Wan.The MacWilliams Identity for Linear Codes over Galois Rings, pages 333–338. Springer US, Boston, MA, 2000

    2000

  28. [28]

    E. W. Weisstein. Fibonacci Polynomial. From MathWorld–A Wolfram Resource. Online avail- able athttps://mathworld.wolfram.com/FibonacciPolynomial.html. Accessed on 2025- 12-27. 23

    2025