Metraipolis › archive › dc_182ad785ebad

Almost all graphs are determined by their generalized spectrum — arXiv:2610.11047

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.11047
License (as archived)
CC0-1.0
Archived
2026-10-09T06:29:00.965Z
SHA-256 of the archived text
7c54fa72ce403432fd7bf4c99e285d5570c3dca8e1ab88b4c1d72a9fa86c3138
Stable URL of this page
https://metraipolis.com/documento/dc_182ad785ebad

How to cite

Almost all graphs are determined by their generalized spectrum — arXiv:2610.11047 — arXiv (en), https://arxiv.org/abs/2610.11047 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_182ad785ebad (Metraipolis archive dc_182ad785ebad, sha256 7c54fa72ce403432fd7bf4c99e285d5570c3dca8e1ab88b4c1d72a9fa86c3138)
BibTeX
@misc{dc182ad785ebad,
  title = {Almost all graphs are determined by their generalized spectrum — arXiv:2610.11047},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.11047},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_182ad785ebad; sha256 7c54fa72ce403432fd7bf4c99e285d5570c3dca8e1ab88b4c1d72a9fa86c3138},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11047. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\pm1$ matrix with zero diagonal.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.11047 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:53:57.119Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).