Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs

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ős-Rényi 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.

Disclosure

“Trevisan for suggesting, several years ago, the problem of determining the spectral gap of Erdős-Rényi hypergraphs. LP’s work on this project was supported by the Swiss National Science Foundation, grant no. 10004947. The authors used AI tools for literature research and to scan the manuscript for typos. All content was written and verified by the authors. 2 Preliminaries Asymptotic notation: We write a ≲ b (resp. a ≳ b) to denote a ⩽ Cb (resp. a ⩾ Cb) for some universal c”

PDF page 7

Classification

Literature search

Multiplier

2

Verified

2026-08-24T00:34:15.228Z

Structural counts