Paperlane

no. 13 · Wednesday 11 November 2026

Almost all graphs are determined by their generalized spectrum

Ziqing Xiang

math.CO · v2 · □ lean

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

comments
1. Lean formalization is available at Palomar Registry now. https://palomar-registry.org/entry?id=PALOMAR-2026-10-23-000011 2. The introduction has been revised a bit. No other sections are modified. 3. I am collaborating with Nikita Lvov and Alexander Van Werde, working on a simplification and rewrite of the paper. https://almost-all-dgs.net/
fields
Combinatorics
pdf ↗ page arXiv:2610.11047 ↗