On the satisfaction frequency of spectral characterization conditions

1. Problem Statement

The paper addresses a fundamental open problem in algebraic graph theory: Haemers' Conjecture. This conjecture posits that almost all graphs are uniquely determined by their adjacency spectrum (i.e., they have no non-isomorphic "cospectral mates"). While it is known that cospectral graphs exist, the probability of a random graph being cospectral is believed to vanish as the number of vertices $n \to \infty$.

Current research has established sufficient conditions (e.g., Wang and Xu, Wang and Yu) that guarantee a graph is uniquely characterized by its spectrum. However, the probabilistic frequency with which these conditions are satisfied by random graphs is poorly understood. Existing bounds on the number of such graphs are constructive but yield vanishing fractions of all possible graphs. Numerical evidence suggests these conditions hold with non-vanishing frequency, but no rigorous theoretical limits or specific conjectures for these probabilities have been formulated, particularly for symmetric integer matrices (adjacency matrices).

2. Methodology

The authors develop a novel two-step framework connecting spectral graph theory to abstract-algebraic random matrix statistics.

Step 1: Algebraic Rephrasing

The authors rephrase the sufficient conditions for spectral characterization in terms of the structure of $\mathbb{Z}[x]$-modules associated with the adjacency matrix $M$.

• Walk Matrix Condition: The condition that the determinant of the walk matrix $W = [\zeta, M\zeta, \dots, M^{n-1}\zeta]$ is square-free is rephrased as a constraint on the cokernel of the module $\text{coker}(M - xI, \zeta)$. Specifically, it relates to whether the module is trivial or isomorphic to $\mathbb{F}_p[x]/(x-a)$ for specific primes $p$.
• Discriminant Condition: The condition that the discriminant of the characteristic polynomial is odd and square-free is rephrased in terms of the structure of $\text{coker}(M - xI)$. This involves analyzing the module's behavior modulo $p$ and its length relative to irreducible polynomials in $\mathbb{F}_p[x]$.

Step 2: Profinite Random Matrix Ensembles

To analyze the distribution of these modules, the authors introduce an analytically tractable random matrix model:

• The Model: Instead of sampling matrices from $\{0, 1\}$, they sample symmetric matrices $M$ from the profinite completion of $\mathbb{Z}[x]$, denoted $\widehat{\mathbb{Z}[x]}$, equipped with the Haar probability measure.
• Symmetry: The model preserves the symmetry constraint ($M = M^\top$) essential for adjacency matrices.
• Invariance: The Haar measure on this profinite ring possesses a strong invariance property: if $M$ is drawn from the ensemble and $G$ is an invertible matrix over the ring, then $GMG^\top$ has the same distribution as $M$.
• Reduction: Using this invariance and the structure of Noetherian local rings, the authors prove that the distribution of the cokernel of an $n \times n$ matrix, conditioned on its rank, reduces to the distribution of the cokernel of a much smaller matrix (size $k \times k$ where $k$ is the corank). This allows the limiting probabilities to be computed via finite algebraic calculations.

3. Key Contributions

1. First Specific Conjectures: The paper provides the first rigorous, well-motivated conjectures for the limiting satisfaction frequencies of spectral characterization conditions.
2. Theoretical Framework: It establishes a bridge between spectral graph theory and the arithmetic statistics of random matrices over profinite rings, generalizing previous work on non-symmetric matrices (directed graphs) to the symmetric case.
3. Universality Hypothesis: The authors argue that these limiting probabilities are universal for random graphs (entries in $\{0,1\}$) provided the entries are not concentrated on specific residue classes, similar to universality in random matrix theory (e.g., Gaussian ensembles).

4. Main Results

The paper derives explicit limiting probabilities for two distinct conditions as $n \to \infty$.

A. Walk Matrix Condition (Square-free Determinant)

Based on the condition that $\det(W)$ is square-free (Theorem 1.3), the authors conjecture the limiting probability for a random symmetric matrix with $\{0,1\}$ entries and a random vector $\zeta$:
$$\lim_{n \to \infty} \mathbb{P}(\det(W) \text{ is square-free}) = \prod_{p} \left( 1 - \frac{1}{p^2} - \frac{1}{p^3} + \frac{1}{p^4} \right) \prod_{k=1}^{\infty} \left( 1 - \frac{1}{p^{2k}} \right) \approx 0.2943$$

• Validation: Numerical simulations (Table 1) show excellent agreement with this theoretical prediction up to at least the third significant digit.
• Comparison: This differs significantly from the heuristic $1 - 1/p^2$ expected for random integers, highlighting the structural constraints of the walk matrix.

B. Discriminant Condition (Odd and Square-free)

Based on the condition that the discriminant $\Delta_M$ of the characteristic polynomial is odd and square-free (Theorem 1.6), the authors derive:
$$\lim_{n \to \infty} \mathbb{P}(\Delta_M \text{ is odd and square-free}) = \frac{6}{7} \prod_{p} \left( 1 - \frac{1}{p^2} \frac{3p-1}{p+1} \right) \prod_{k=1}^{\infty} \left( 1 - \frac{1}{p^{2k}} \right) \approx 0.1686$$

• Validation: Numerical simulations (Table 2) confirm this prediction.
• Note: The condition for $p=2$ is distinct (requiring the discriminant to be odd), while for odd primes, it requires square-freeness.

5. Significance and Implications

• Beyond Constructive Bounds: The results suggest that a constant fraction (approx. 16.8% to 29.4%) of random graphs satisfy sufficient conditions for being uniquely determined by their spectrum. This implies that the set of graphs characterized by spectrum is much larger than what current constructive methods (which yield bounds like $e^{cn}$) can prove.
• New Analytical Tools: The use of profinite completions and Haar measures provides a powerful new toolkit for studying arithmetic properties of random matrices, particularly those with symmetry constraints, which are notoriously difficult to analyze using standard probabilistic methods.
• Future Directions: The paper identifies "universality" as the remaining technical hurdle to turning these conjectures into theorems for $\{0,1\}$ matrices. It also notes exceptional behaviors related to the prime $p=2$ and specific deterministic vectors (like the all-ones vector), suggesting rich algebraic structures remain to be explored.

In summary, this work transforms the study of spectral characterization from a purely combinatorial or numerical endeavor into a rigorous probabilistic framework, offering precise predictions for the frequency of unique spectral determination in random graphs.