Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 59 min ago
PreprintCC BY 4.0arXiv

Almost all graphs are determined by their generalized spectrum

  • Ziqing Xiang
Open at sourcePDFDOICite

Abstract

Haemers' conjecture for the generalized spectrum asserts that almost all graphs are determined by their generalized spectrum, that is, for almost all graphs G, every graph with the same spectrum as G whose complement has the same spectrum as the complement of G is isomorphic to G. We prove this conjecture by showing that the random graph G(n,1/2) is determined by its generalized spectrum with probability tending to one. The proof combines a local theory of the denominators of the rational orthogonal matrices that relate generalized cospectral graphs, Fourier analysis of random symmetric matrices over finite rings, Seidel switching, inverse Littlewood--Offord theory over finite fields, rank estimates for random symmetric matrices modulo primes, and a study of the rational factors of the characteristic polynomial of a random symmetric ±1 matrix with zero diagonal.

Related

  1. A New Sufficient Condition for Oriented Graphs Determined by Their Generalized Skew Spectra
    Limeng Lin, Wei Wang, Wei Wang +1
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Finite Matrix Rings of Even Size Are Determined by Their Commuting Graphs
    Hamid Shahverdi, Vahid Shahverdi
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Cantor Spectrum via a Reducibility-Duality Bridge for the Mosaic Almost Mathieu Operator
    Jiawei He, Yuan Shan, Yongjian Wang
    arXivPreprintarXiv licenceFull textDynamical systemsMathematical physicsarXiv
  4. Inference for Generalized Almost Cyclostationary Processes with Unknown Lag-Dependent Cycle Frequencies
    Anna E. Dudek, Antonio Napolitano, Jakub Rutkowski +1
    HALPreprintCC BY 4.0Full textStatisticsHAL
  5. Almost Every Graph Is Reconstructible from Its Token Graphs
    Yuanming Luo
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{xiang2026almost,
  title = {{Almost all graphs are determined by their generalized spectrum}},
  author = {Ziqing Xiang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.11047},
  eprint = {2610.11047},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.11047},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Almost all graphs are determined by their generalized spectrum
AU  - Ziqing Xiang
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.11047
UR  - https://arxiv.org/abs/2610.11047
AB  - Haemers' conjecture for the generalized spectrum asserts that almost all graphs are determined by their generalized spectrum, that is, for almost all graphs G, every graph with the same spectrum as G whose complement has the same spectrum as the complement of G is isomorphic to G. We prove this conjecture by showing that the random graph G(n,1/2) is determined by its generalized spectrum with probability tending to one. The proof combines a local theory of the denominators of the rational orthogonal matrices that relate generalized cospectral graphs, Fourier analysis of random symmetric matrices over finite rings, Seidel switching, inverse Littlewood--Offord theory over finite fields, rank estimates for random symmetric matrices modulo primes, and a study of the rational factors of the characteristic polynomial of a random symmetric ±1 matrix with zero diagonal.
ER  -