Almost all graphs are determined by their generalized spectrum
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Almost all graphs are determined by their generalized spectrum".
Emmy: Here's the gist of the paper. Almost all graphs are determined by their generalized spectrum (DGS), meaning almost all graphs in G(n, 1/2) are DGS with probability tending to one as n to infinity.
Ada: The proof establishes this by showing that the event that a graph G is DGS is equivalent to the event that no matrix in QG has a level of at least 2, which simplifies to showing every matrix in QG has level 1.
Emmy: The overall strategy relies on five key components: 1.
Ada: Theorem 2.2 excludes local failures of large degree at all odd primes for d at least 3 2 n.
Paper summary: Ada: So, wrapping up this talk on "Almost all graphs are determined by their generalized spectrum," we see they've managed to build a very solid probabilistic argument >
Emmy: They proved that the random graph G(n, one/two) is determined by its generalized spectrum with probability one as n goes to infinity > <ref:2610.11047#pg1,that the random graph G(n, 1/2) is determined by its>
Kolya: And the key takeaway is that this isn't just about a few special graphs; it's about the overwhelming majority of graphs exhibiting this property >
Ada: Exactly. The paper shows that controlling eigenvalue distributions modulo different primes, bounding repeated factors through discriminant bounds, and using Fourier analysis to control vector properties all combine to exclude local failures across all relevant scales >
Emmy: It really confirms that we can have a very strong structural statement about random graphs based on their spectrum, provided we account for the arithmetic details carefully >
Kolya: The limitation they mention is that this whole argument relies on those five component theorems, Theorems two point two through two point six > <ref:2610.11047#pg3,five component theorems, Theorems 2.2>
Ada: And one of those limitations is that they are excluding local failures based on specific definitions related to invariant subspaces modulo p, so the analysis is tightly coupled to those structural conditions >
Emmy: What this means for us is that we have a robust framework for understanding graph isomorphism through spectra, but it shows exactly where the reliance on these underlying arithmetic structures lies >
Conclusion: Ada: So, we've been looking at how these random graphs behave when you look at their generalized spectrum, and now we’re wrapping up on what this paper actually says about them >
Emmy: It boils down to saying that for almost any graph you pick from that random distribution, its entire structure is locked in by the numbers in its spectrum >
Ada: The authors of this paper are tackling a really deep question about what makes a graph uniquely identifiable using just the eigenvalues and their relationships >
Emmy: They prove that the probability of picking a graph that *isn't* determined by its generalized spectrum tends to zero as you increase the number of vertices, n >
Ada: And they do this by showing that they can control those tricky local failures across all possible scales, using these five specific theorems we talked about >
Emmy: It’s like they built a giant net, and this net catches every possible way a graph could fail to be determined by its spectrum across the board >
Ada: So what does this mean for us on the radio? It means that if you generate a random graph at scale n, you can trust that its spectrum will tell you almost exactly how it's built >
Emmy: It suggests that the generalized spectrum is a very powerful fingerprint for random graphs, and it’s not just some coincidence; it's tied to the underlying arithmetic of those matrices >
Southern University of Science and Technology
math.CO
Submitted: 2026-10-08
Updated: 2026-11-10
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/
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: Almost all graphs are determined by their generalized spectrum (DGS), meaning almost all graphs in G(n, 1/2) are DGS with probability tending to one as n to infinity.
Key concepts
- Generalized Spectrum (DGS)
- A property of a graph related to its spectrum that almost all graphs possess. The paper shows this property holds with high probability because it is equivalent to ensuring no matrix in QG has a level greater than 1, simplifying the condition significantly.
- Level of a Matrix
- A measure used in the proof to check if a matrix has certain structural properties. The core argument is that for a graph to be DGS, every relevant matrix must have this level equal to 1. Controlling this level is central to proving the main result.
- Seidel Switching
- A technique used in the analysis that replaces the fixed all-ones vector with a random sign vector. This allows researchers to estimate local failures conditionally, which helps in bounding and controlling the probability of undesirable graph structures occurring.
- Discriminant Module (D)
- A mathematical structure decomposed into local components ($T_m$) whose properties control divisibility by primes. Analyzing these components, such as determining if they are chain rings, is crucial for bounding repeated factors in characteristic polynomials.
Terminology
Summary
Almost all graphs are determined by their generalized spectrum (DGS), meaning almost all graphs in G(n, 1/2) are DGS with probability tending to one as n to infinity. p. 0 Almost all graphs are determined by their generalized spectrum
Ziqing Xiang ∗
Southern University of Science and Technology
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. 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.Where the paper says it
Where the paper says it
The overall strategy relies on five key components:
-
Theorem 2.2 excludes local failures of large degree at all odd primes for d at least 3 2 n. p. 2
Where the paper says it
The remaining sections contain the proofs of the components. After the preliminaries of Section 3, Section 4 excludes local failures of large degree at all odd primes (Theorem 2.
-
Theorem 2.3 controls the arithmetic of levels, showing that the probability that some matrix in QG other than a permutation matrix has a level whose prime factors are all small tends to zero, by utilizing anti-concentration tools and analyzing the walk matrix modulo small primes. p. 0
Where the paper says it
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. Contents 1 Introduction 2 2 Proof strategy 5 3 Mates, local failures and Seidel switching 12 4 Reduction to a single random Seidel matrix 19 5 Lattices, local components and levels 24 6 Fourier analysis modulo p E and short vectors 31 7 Small primes: first moments and tightness 36 8 The prime 2 41 9 No mates with smooth levels 50 10 Anti-concentration tools 52 11 Eigenvalues in Fp 64 12 Eigenvalues in Fp2 74 13 Eigenvalues of degree at least three 79 ∗Email: xiangzq@sustech.
-
Theorem 2.4 excludes local failures for moderate degrees below 3 2 n at odd primes, using Fourier analysis modulo p and results on random symmetric matrices. p. 0
Where the paper says it
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. Contents 1 Introduction 2 2 Proof strategy 5 3 Mates, local failures and Seidel switching 12 4 Reduction to a single random Seidel matrix 19 5 Lattices, local components and levels 24 6 Fourier analysis modulo p E and short vectors 31 7 Small primes: first moments and tightness 36 8 The prime 2 41 9 No mates with smooth levels 50 10 Anti-concentration tools 52 11 Eigenvalues in Fp 64 12 Eigenvalues in Fp2 74 13 Eigenvalues of degree at least three 79 ∗Email: xiangzq@sustech.
-
Theorem 2.5 addresses huge primes by stating that the characteristic polynomial of a random symmetric plus or minus 1 matrix with zero diagonal has no rational factor of small degree, achieved by bounding candidate factors and using rank estimates. p. 0
Where the paper says it
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. Contents 1 Introduction 2 2 Proof strategy 5 3 Mates, local failures and Seidel switching 12 4 Reduction to a single random Seidel matrix 19 5 Lattices, local components and levels 24 6 Fourier analysis modulo p E and short vectors 31 7 Small primes: first moments and tightness 36 8 The prime 2 41 9 No mates with smooth levels 50 10 Anti-concentration tools 52 11 Eigenvalues in Fp 64 12 Eigenvalues in Fp2 74 13 Eigenvalues of degree at least three 79 ∗Email: xiangzq@sustech.
-
Theorem 2.6 excludes local failures for primes p > e(n) at degrees d at least 1, using arguments involving invariant subspaces and discriminant bounds on repeated factors. p. 5
Where the paper says it
The arguments at the moderate primes need p ≥ n 2/5 in the degrees d ≥ 3, which is why ε < 1 10 , and the argument at the huge primes works for all p > e(log n) 6 . Local failures of large degree, namely of degree at least 3 log2 n, are excluded with probability 1 − o(1) at all odd primes at once by a simpler argument, and this is the first component.
The proof integrates arithmetic approaches (like those of Wang) with random matrix theory over finite fields and integers, utilizing tools such as Seidel switching to replace the fixed all-ones vector with a random sign vector, which allows local failures to be estimated conditionally. p. 0 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. Contents
1 Introduction 2
2 Proof strategy 5
3 Mates, local failures and Seidel switching 12
4 Reduction to a single random Seidel matrix 19
5 Lattices, local components and levels 24
6 Fourier analysis modulo p
E and short vectors 31
7 Small primes: first moments and tightness 36
8 The prime 2 41
9 No mates with smooth levels 50
10 Anti-concentration tools 52
11 Eigenvalues in Fp 64
12 Eigenvalues in Fp2 74
13 Eigenvalues of degree at least three 79
∗Email: xiangzq@sustech. modulo 2 one vector at a time, building on the analysis of the walk matrix modulo 2
by Wang (2013, 2017) [58, 59]. This shows that, for every d0 ≥ 2, the local components above 2 of
degree at least d0 are chain rings, except with probability O(2−d0 ) + o(1) (Proposition 8.Where the paper says it
Where the paper says it
The detailed analysis of specific theorems shows:
-
Theorem 2.3 is proven by bounding the expected number of vectors with bounded norms and showing that for fixed prime factors, the corresponding local component is not a chain ring unless specific Krylov data conditions are met. p. 8
The analysis also separately addresses p=2. p. 4Where the paper says it
With the local theory in hand, it suffices to show that, with high probability, only a bounded number of local components above the small primes can contribute to a level, that their exponents and the multiplicities of the corresponding factors of ¯φ are bounded, and that the short integer vectors produced below by a matrix of bounded level do not exist. At the odd small primes we bound the probabilities of local failures by Fourier analysis modulo p, and at every fixed prime, including 2, we bound the exponents of coker W by Fourier analysis modulo powers of p (Sections 6 and 7), with the character method for random matrices of Wood (2017) [69] and Nguyen–Wood (2025) [39].
Where the paper says it
1 is equivalent to the statement that, with probability 1 − o(1), no matrix in QG has level at least 2. We examine the prime factors of the levels separately, and for a given prime p we ask whether p divides the level of some matrix in QG.
-
The proof concerning characteristic polynomials shows that with high probability, a random Seidel matrix has no rational factor of small degree (up to eta in (0, 1/27)), by bounding the number of candidate factors and using prime distribution bounds.
-
Theorem 2.4 is established by showing that the probabilities of local failures E(d)p for d=1, d=2, or 3 at most d < 3 2 n tend to zero, relying on Propositions 11. p. 5
8 and 12.4 concerning degrees in pi at least 5n and pi'n.Where the paper says it
This is not small at a fixed prime, and we cannot hope to exclude local failures there. Summed over all d and all primes above n 1/2−ε , where ε > 0 is small and fixed, these probabilities tend to 0, and we show that with probability 1 − o(1) no local failure occurs at any of these primes (Section 2.
-
Theorem 2.6 is proven by showing that for primes p > e(n) 6, the absence of rational factors of small degree implies bounds on the discriminant module, leading to a bound on beta(T) that excludes local failures. p. 0
Where the paper says it
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. Contents 1 Introduction 2 2 Proof strategy 5 3 Mates, local failures and Seidel switching 12 4 Reduction to a single random Seidel matrix 19 5 Lattices, local components and levels 24 6 Fourier analysis modulo p E and short vectors 31 7 Small primes: first moments and tightness 36 8 The prime 2 41 9 No mates with smooth levels 50 10 Anti-concentration tools 52 11 Eigenvalues in Fp 64 12 Eigenvalues in Fp2 74 13 Eigenvalues of degree at least three 79 ∗Email: xiangzq@sustech.
In summary, the final result confirms that for G(n, 1/2), the probability that it is DGS tends to 1 as n to infinity, built upon controlling eigenvalue distributions modulo p, bounding repeated factors via discriminant bounds, and using Fourier analysis to control vector properties.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Enhanced determination of graphs by generalized spectrum: The system can determine if a graph is determined by its generalized spectrum with high probability for random graphs G(n, 1/2) based on Theorem 1.1, leveraging Fourier analysis and results on random symmetric matrices over finite rings to control the denominators of relating orthogonal matrices.
-
Probabilistic identification of generalized cospectral mates: The system can use the components of the proof to show that with probability tending to one, no generalized cospectral mate exists for a controllable graph G(n, 1/2) whose level is divisible by a prime outside a specified range Rn(delta).
-
Precise control over local failure events: The system can detect and bound local failures E(d)p at odd primes p using the anti-concentration tools derived from inverse Littlewood-Offord theory and Fourier analysis modulo p, which are controlled by the first moment estimates in Theorem 7.1.
-
Tight bounds on spectral invariants: The system can establish that for fixed primes and degrees, the exponents of components of coker W and multiplicities of irreducible factors of A modulo p are tight in probability uniformly in n, as stated in Proposition 7.2.
-
Detection of short vectors in kernels: The system can identify if a column z of a graph Q has small weight wt(z) and is killed by a polynomial g(A bar) using the tools from Section 6, which provides bounds on the probability that such vectors exist (Lemma 6.5).
-
Characterization of graph structure via lattice theory: The system can use the discriminant module D and its local components Tm to determine if a graph Q has a small level by checking if Tm is not a chain ring, as described in Proposition 5.6(ii) and Corollary 5.7.
-
Robustness testing for spectral invariants: The system can test if the simple submodules of type beta are robust against small perturbations by analyzing the Gram data of random matrices using Lemma 6.6, which ensures that vectors with weight less than sdelta do not exist with high probability.
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 plus or minus1 matrix with zero diagonal.
Sources
- On the satisfaction frequency of spectral characterization conditions
- On the levels of rational regular orthogonal matrices for generalized cospectral graphs
- Square-free Discriminants of Matrices and the Generalized Spectral Characterizations of Graphs
- Almost all graphs have no cospectral mate with fixed level
- Natural graph spectra
- Almost all graphs have no cospectral mates with height relative small to its order
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality