On the satisfaction frequency of spectral characterization conditions
Nikita Lvov ⋄ \diamond Alexander Van Werde ∗ \ast · 2026
Read On the satisfaction frequency of spectral characterization conditions by Nikita Lvov ⋄ \diamond Alexander Van Werde ∗ \ast (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26932.txt.
Introduction
Lvov and Van Werde ask how often a graph is pinned down by spectral data alone. They give the first sharp conjectures on how often two sufficient conditions hold. Their framework recasts the conditions with modules over polynomial rings tied to the adjacency matrix. Random matrix ensembles over profinite completions make the module spread tractable. One condition needs the walk matrix determinant to be square-free. The other uses the discriminant of the characteristic polynomial. The method turns a graph question into module statistics.
Catalog record
| CREATOR | Nikita Lvov ⋄ \diamond Alexander Van Werde ∗ \ast |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132461 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.26932
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the satisfaction frequency of spectral characterization conditions Nikita Lvov ⋄ \diamond Alexander Van Werde ∗ \ast Abstract . We give the first specific conjectures on how frequently graphs satisfy sufficient conditions for being uniquely characterized by spectral information. These conjectures arise from a theoretical framework that we developed based on abstract-algebraic random matrix statistics. Specifically, we rephrase conditions from the literature in terms of ℤ [ x ] \mathbb{Z}[x] -modules associated to the adjacency matrix, and study the distribution of those modules in analytically tractable profinite random matrix ensembles. We applied this new method to two distinct conditions. The first requires square-freeness of the determinant of the walk matrix, and the second uses the discriminant of the characteristic polynomial. 1. Introduction It has been known since the 1950s that there exist non-isomorphic graphs whose adjacency matrices have the same characteristic polynomial, called cospectral mates [ 13 ] . A fundamental conjecture by Haemers however proposes that such examples should be atypical [ 24 , 44 ] . That is, if one picks a graph on n nodes uniformly at random, then it is believed that the probability of cospectrality tends to zero as n\to\infty . A closely related fingerprint conjecture for matrices with entries \pm 1 was more recently also proposed by Vu [ 50 , 49 ] . Haemers’ conjecture remains open. The current best lower bound on the number of graphs characterized by spectrum is by Koval and Kwan [ 30 ] who established that at least \exp(cn) graphs on n nodes are characterized by adjacency spectrum for some c>0 . This was a significant improvement on previous bounds of order \exp(c\sqrt{n}) , but remains a vanishing fraction of all (1-o(1))2^{n(n-1)/2}/n!\geq\exp(cn^{2}) graphs. Moreover, it seems likely that an exponential bound is the limit of the constructive methods in [ 30 ] and that even bounds of order \exp(n^{1+\varepsilon}) would require different methods: “…It is hard to imagine a natural argument that could reconstruct so many different graphs… Instead, it seems that non-constructive methods may be necessary…” [ 30 , §1.1] . There indeed exist sufficient conditions that can certify that a graph is determined by spectral information without giving an algorithm to reconstruct the graph from its spectrum. Such conditions were first discovered by Wang and Xu [ 54 ] for a generalized notion where one is also given the spectrum of the complement graph, and considerable effort has since been devoted to refinements of these sufficient conditions [ 51 , 38 , 52 , 53 , 23 , 56 , 55 , 6 , 60 , 47 ] . (We give examples in Section 1.1 .) Numerical investigations suggest that such sufficient conditions are applicable with non-vanishing frequency. This would be significant considering the expected limits of constructive methods. Unfortunately, the current theoretical understanding of the probabilistic behavior of the conditions is also limited. For instance, while the satisfaction frequencies of the conditions can be roughly estimated numerically, it is not known for any of them what the exact limiting values might be. The present paper takes an initial step towards a probabilistic understanding of spectral characterization condition by developing a connection to the theory of abstract-algebraic random matrix statistics. Our approach has two main steps. The first is to rephrase the considered condition in terms of an abstract-algebraic object associated to the graph’s adjacency matrix, such as certain groups or a modules. The second step is to study the distribution of those algebraic objects using an analytically tractable profinite random matrix ensemble. The ensemble used in this second step incorporates the symmetry constraint on the adjacency matrix that comes from the the graph being undirected, while achieving analytical tractability by taking the entries uniform on a larger space than \{0,1\} . In particular, the results achieved in the latter model give theoretical insight on the limiting satisfaction frequency of various conditions; see Theorems 4.11 and 4.17 . Our main results require some technical background to motivate and state, which we build up over the span of the paper. A notable and easy-to-state consequence is that we find the first specific predictions on the satisfaction frequency of spectral characterization conditions. The resulting conjectures are showcased in Section 1.1 . We explain the framework that we developed in Section 1.2 and comment on universality in Section 1.3 . The remainder of the paper is outlined in Section 1.4 . 1.1. Specific predictions for satisfaction frequencies To demonstrate the flexibility of our approach, we consider two different conditions. The first is based on the square-freeness of the determinant of the walk matrix and is the subject of 1.4 . The second uses the discriminant of the characteristic polynomial and is considered in 1.7 . 1.1.1. Conditions based on the walk matrix The following definitions are due to Farrugia [ 18 ] and Qiu, Ji, Mao, and Wang [ 37 ] in a special case; see also [ 47 , 55 ] for the general setting used here. Definition 1.1 . Consider an integer vector \zeta\in\mathbb{Z}^{n} and a matrix \mathbf{M}\in\mathbb{Z}^{n\times n} that is symmetric \mathbf{M}=\mathbf{M}^{\top} . Two such pairs (\mathbf{M},\zeta) and (\mathbf{N},\eta) are isomorphic up to signed permutation if there exists a signed permutation \mathbf{S} such that \mathbf{N}=\mathbf{S}\mathbf{M}\mathbf{S}^{\top} and \mathbf{S}\zeta=\zeta . Here, a signed permutation is a matrix of the form \mathbf{S}=\mathbf{P}\mathbf{D} with \mathbf{P} a permutation and \mathbf{D} a diagonal matrix with entries \pm 1 . The signs serve to avoid trivial obstructions to spectral characterization for general integer matrices, but are irrelevant if one restricts to the adjacency matrices of a graphs as two nonnegative matrices are related by a signed permutation if and only if they are related by an unsigned permutation. Consequently, since permutations corresponds to graph isomorphism, the following notion yields a generalization of adjacency spectral characterization, with some additional information related to the vector \zeta : Definition 1.2 . The bivariate characteristic polynomial of the pair (\mathbf{M},\zeta) is defined as (1.1) \displaystyle\Phi_{\mathbf{M},\zeta}(\lambda,t)\vcentcolon=\det\bigl(\lambda\mathbf{I}-\mathbf{M}-t\zeta\zeta^{\top}\bigr), where \mathbf{I} is the identity. The pair (\mathbf{M},\zeta) is said to be characterized by \Phi -spectrum if every (\mathbf{N},\eta) with \Phi_{\mathbf{M},\zeta}=\Phi_{\mathbf{N},\eta} is isomorphic up to signed permutation. The case where \zeta=\mathbbm{1}_{S} is the indicator vector of some set S\subseteq\{1,\ldots,n\} and \mathbf{M} is the adjacency matrix of a graph admits a direct graph-theoretic interpretation. Then, the differentiating information in \Phi_{\mathbf{M},\zeta} can be shown to be equivalent to the pair consisting of the spectrum of \mathbf{M} and the spectrum of the graph on n+1 nodes found by connecting the vertices in S to a new node; see Farrugia [ 18 ] . The special case where \zeta=(1,\ldots,1)^{\top} is the all-ones vector is also known to be equivalent to considering the spectra of the graph and its complement, due to Johnson and Newman [ 27 ] . We consider a sufficient condition in [ 47 , Theorem 2.12] that is a variant on one by Wang [ 51 ] . The walk matrix of (\mathbf{M},\zeta) is the square matrix \mathbf{W}\in\mathbb{Z}^{n\times n} with columns \zeta,\mathbf{M}\zeta,\ldots,\mathbf{M}^{n-1}\zeta . The terminology refers to the fact that if \zeta=\mathbbm{1}_{S} is an indicator vector and \mathbf{M} is the adjacency matrix of a graph, then the ij th entry \mathbf{W}_{i,j} counts walks of length j-1 that start in vertex i and