We study the spectrum of the adjacency matrix $A_n$ of directed inhomogeneous random graphs on $n$ vertices. We assume that $A_n$ has independent entries and diverging average degree scale $s_n$. This framework includes, as special cases, the directed Chung--Lu random graph and directed stochastic block models. Assuming boundedness of the variance profile and that $s_n$ diverges faster than a suitable logarithmic function of $n$, we show that the rank-one Chung--Lu model satisfies a non-homogeneous version of the circular law, which in some situations allows for an explicit expression. Moreover, under mild conditions, we identify the asymptotic singular value distribution using tools from free probability. Finally, for finite-rank directed models, we prove the existence of eigenvalues outside the bulk and establish their joint Gaussian fluctuations at the scale $\sqrt{s_n/n}$, with an explicit covariance matrix. These results extend the theory of spectral outliers and their fluctuations to directed inhomogeneous random graphs.
The Watts-Strogatz random graph model on $n$ vertices with parameters $K$ (a positive even integer) and $p \in [0, 1]$ is constructed in two steps. First, one starts with a ring lattice on $n$ vertices, where each vertex is connected to its $K/2$ nearest neighbors on each side. Each edge in turn is then independently rewired with probability $p$ by replacing one endpoint with a uniformly chosen vertex not already adjacent to it. We study the empirical eigenvalue distribution of the adjacency matrix for this model, whose entries are highly dependent due to the rewiring construction. In the regime where both $K$ and $pK$ grow to infinity with the vertex size $n$, we show that, after appropriate scaling, the empirical eigenvalue distribution converges to the semicircle law. The proof is based on a novel coupling argument that approximates the adjacency matrix by a sum of two independent random matrices, one a sparse Wigner matrix and the other a random band matrix. In the case where $K$ and $p$ remain fixed, we propose conjectural formulas for the first five moments of the limiting eigenvalue distribution. These conjectures are supported by a convergence result relating the Watts-Strogatz model to another random graph model, together with numerical simulations.
A sequence of sparse weighted graphs $(G_N:N\ge 1)$ indexed by the number of vertices $N$ is said to be left-convergent if all (suitably weighted) subgraph counts converge to a limit as $N\to\infty$. This notion generalizes in a natural way Benjamini-Schramm's definition of local weak convergence. A broad research agenda aims at determining which `global'graph properties are determined by left or local weak convergence (in other words, which of these properties are in fact local). We prove that, under a spectral condition on the weighted adjacency matrix ${\boldsymbol A}_N$ of graph $G_N$, the free energy density of the Ising model on this weighted graph is continuous in the left convergence topology (and hence is a local function). Our proof uses the decomposition of the Ising measure as a log-concave combination of product measures, and of the rapid mixing of Langevin dynamics for log-concave measures. As applications, we derive new limit theorems for the free energy density of spin glasses, antiferromagnets, and magnetization constrained ferromagnetic models, on locally tree-like graphs.
We prove universality of limiting local eigenvalue statistics for random matrices over $\mathbb{Z}_p$. In previous work of the author and Van Peski (arXiv:2601.06283), the limiting eigenvalue correlation functions of additive Haar random matrices were studied in arbitrary finite extensions of $\mathbb{Q}_p$. The same Haar random matrix model plays a central role in the Ellenberg-Jain-Venkatesh heuristic for zeros of $p$-adic $L$-functions. We show that its limiting local eigenvalue statistics are unchanged for a broad class of random matrices with independent entries satisfying a mild non-concentration condition. Thus the random matrix predictions underlying the Ellenberg-Jain-Venkatesh heuristic are not artifacts of the particular Haar ensemble, but instead reflect universal limiting eigenvalue statistics. In this sense, our results provide additional theoretical support for the robustness of their random matrix heuristic. Our proof is based on a new framework, which we call the resultant distribution method. The method recovers limiting laws and root statistics of $p$-adic polynomials from the distributions of their resultant valuations against fixed test polynomials, together with suitable degree estimates. As a second application, we consider random $p$-adic polynomials with independent coefficients satisfying a mild non-concentration condition. Caruso (arXiv:2110.03942) determined the joint root correlation functions of the Haar coefficient model over finite extensions of $\mathbb{Q}_p$. We prove that, for roots of absolute value one, these limiting correlation functions are universal and persist for a broad class of independent coefficient distributions.
For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche--Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.
We study self-avoiding walks on the canonical one-sided graphs of Lindstrom nested fractals. We prove that the connective constant $\mu$ exists and identify $\log\mu$ with the critical inverse temperature of a finite-dimensional boundary-state renormalization. If the boundary-state partition vectors are bounded at criticality, then the fixed-length counts $c_n$ satisfy two-sided polynomial bounds around $\mu^n$. We also prove that $h$-flexibility implies $c_{n+h}/c_n\to\mu^h$. For regular polygonal $N$-gaskets, we derive exact crossing recursions, determine the smallest flexibility step $h$, and obtain explicit algebraic connective constants for the $6$- and $9$-gaskets. The Vicsek graph has no flexibility step, and its successive ratios do not converge.
For a graph $G$, let $s^+(G)$ and $s^-(G)$ denote the sums of the squares of its positive and negative adjacency eigenvalues. We determine all equality cases in the conjecture of Elphick, Farber, Goldberg, and Wocjan that every connected graph $G$ on $n$ vertices satisfies \[ \min \{s^+(G),s^-(G)\}\ge n-1. \] Namely, equality for $s^+$ holds exactly for trees, whereas equality for $s^-$ holds exactly for trees and complete graphs. The proof combines the $P_3$-removal lemma in the no-cut-vertex case with a detailed equality analysis of the underlying doubly nonnegative matrix inequality. Every block is forced to be complete, and a minimal-counterexample argument gives an exact rank-one decomposition of the folded matrix $M^c$. The resulting non-edge vanishings, together with $AX=XA$, rule out an interface between a bridge and a nontrivial block.
Fu-Tao Hu, Yayang Liu, Yi Wang· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
