PreprintarXiv licencearXiv
Low discrepancy and spectral gap for directed hypergraphs via spectral regularity lemma for tensors
Abstract
We show that low discrepancy is equivalent to spectral gap for directed k-uniform hypergraphs. For undirected hypergraphs this recovers a theorem of Lenz and Mubayi, with a considerably shorter proof. At the heart of our argument is a Frieze--Kannan type spectral regularity lemma for hypergraphs based on the variational notion of hypergraph eigenvalues by Friedman--Wigderson, which decomposes any tensor into a bounded number of rank-one tensors plus a quasi-random tensor with small top eigenvalue. This lemma may be of independent interest, and we prove it for complex-valued, not necessarily symmetric tensors. We also briefly discuss a Szemerédi-type variant and the regularization of Cayley-type hypergraphs over finite abelian groups.
Related
- Spectral moments and characteristic polynomials of vertex expansion hypergraphs of graphs
- Spectral extremal hypergraphs without long Berge cycles
- Uniform Hypergraphs with α-Spectral Radius at Most That of a Loose Cycle
- Spectral Turán problems for complete bipartite expansions in linear hypergraphs
- The maximum spectral radius of outerplanar and planar k-uniform hypergraphs
BibTeX
@misc{han2026discrepancy,
title = {{Low discrepancy and spectral gap for directed hypergraphs via spectral regularity lemma for tensors}},
author = {Hiep Han},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37912},
eprint = {2609.37912},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37912},
}
RIS
TY - UNPB
TI - Low discrepancy and spectral gap for directed hypergraphs via spectral regularity lemma for tensors
AU - Hiep Han
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37912
UR - https://arxiv.org/abs/2609.37912
AB - We show that low discrepancy is equivalent to spectral gap for directed k-uniform hypergraphs. For undirected hypergraphs this recovers a theorem of Lenz and Mubayi, with a considerably shorter proof. At the heart of our argument is a Frieze--Kannan type spectral regularity lemma for hypergraphs based on the variational notion of hypergraph eigenvalues by Friedman--Wigderson, which decomposes any tensor into a bounded number of rank-one tensors plus a quasi-random tensor with small top eigenvalue. This lemma may be of independent interest, and we prove it for complex-valued, not necessarily symmetric tensors. We also briefly discuss a Szemerédi-type variant and the regularization of Cayley-type hypergraphs over finite abelian groups.
ER -