It is shown that r-uniform Erd\H{o}s-R\'enyi hypergraphs on n vertices exhibit a spectral gap as soon as their expected number of hyperedges satisfies $m \gg n^{r/2}$.
Abstract
Friedman and Wigderson (1995) introduced a notion of second eigenvalue for hypergraphs that generalizes the second eigenvalue of the adjacency matrix of a graph. We show that $r$-uniform Erd\H{o}s-R\'enyi hypergraphs on $n$ vertices exhibit a spectral gap as soon as their expected number of hyperedges $m$ satisfies $m \gg n^{r/2}$. Prior work identified this scale only up to logarithmic factors; removing these factors is the main technical challenge. Our proof overcomes this obstacle through an explicit decomposition of an associated selector process, inspired by a generic decomposition theorem of Talagrand (2021). As a consequence of our techniques, we obtain improved norm bounds for sparse random tensors with independent entries. Finally, under a mild moment equivalence assumption, we extend to tensors a seminal result of Seginer (2000) for random matrices with i.i.d. entries.
We investigate heavy-Wigner tensors: symmetric random tensors whose independent entries, up to the tensor symmetries, are centered and have moments of order $N^{-(p-1)}$, where $N$ is the tensor dimension. This framework includes normalized adjacency tensors of sparse Erd\H{o}s-R\'enyi hypergraphs and truncated heavy-t...
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 H...
We establish a tensor spectral stability theorem for uniform hypergraphs with bounded matching number. More precisely, for fixed integers $k\geq 3$ and $\beta\geq2$, and sufficiently large $n$, we prove that every $n$-vertex $k$-uniform hypergraph $H$ with matching number at most $\beta$ and tensor spectral radius clos...
The Erd\H{o}s Matching Conjecture concerns the maximum number of hyperedges in an $r$-uniform hypergraph with bounded matching number. In this paper, we study a spectral counterpart of this conjecture. For sufficiently large $n$, we determine the maximum spectral radius over all $n$-vertex $r$-uniform hypergraphs whose...
Liying Kang, Yongchun Lu, Xiying Yuan et al.· 2 citations
The spectral method uses a decoupling argument recently introduced by Kaushik, Romberg, and Muthukumar to control nonlinear error terms to control nonlinear error terms.
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. Assumin...
R. S. Hazra, Giacomo Passuello· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
