EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS

By John Lenz, Dhruv Mubayi. Forum of Mathematics, Sigma, 2012

50 citations recorded by the source corpus.

Let $p(k)$ denote the partition function of $k$. For each $k\geqslant 2$, we describe a list of $p(k)-1$ quasirandom properties that a $k$-uniform hypergraph can have. Our work connects previous notions on linear hypergraph quasirandomness by Kohayakawa, Rödl, and Skokan, and by Conlon, Hàn, Person, and Schacht, and the spectral approach of Friedman and Wigderson. For each of the quasirandom properties that is described, we define the largest and the second largest eigenvalues. We show that a hypergraph satisfies these quasirandom properties if and only if it has a large spectral gap. This answers a question of Conlon, Hàn, Person, and Schacht. Our work can be viewed as a partial extension to hypergraphs of the seminal spectral results of Chung, Graham, and Wilson for graphs.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6ddaa2d391ea7738bff2e6c8f298bb1fe460416d