Eigenvalues and linear quasirandom hypergraphs
From MaRDI portal
Publication:5496786
DOI10.1017/FMS.2014.22zbMATH Open1306.05144arXiv1208.4863OpenAlexW2964115409MaRDI QIDQ5496786FDOQ5496786
Authors: Dhruv Mubayi, John Lenz 
Publication date: 28 January 2015
Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)
Abstract: Let p(k) denote the partition function of k. For each k >= 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 of Kohayakawa-R"odl-Skokan and Conlon-H`{a}n-Person-Schacht and the spectral approach of Friedman-Wigderson. For each of the quasirandom properties that are described, we define a largest and second largest eigenvalue. 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`{a}n-Person-Schacht. Our work can be viewed as a partial extension to hypergraphs of the seminal spectral results of Chung-Graham-Wilson for graphs.
Full work available at URL: https://arxiv.org/abs/1208.4863
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)
Cites Work
- Eigenvalues and expanders
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Expander graphs and their applications
- Spectra of uniform hypergraphs
- Quasi-random graphs
- Some graphs with small second eigenvalue
- On the second eigenvalue of hypergraphs
- Weak hypergraph regularity and linear hypergraphs
- Weak quasi-randomness for uniform hypergraphs
- Quasi-random hypergraphs revisited
- Explicit Concentrators from Generalized N-Gons
- Quasi-random hypergraphs
- Quasirandom Groups
- Spectra of hypergraphs and applications
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- On the spectrum of projective norm-graphs
- Sharp bounds for some multicolour Ramsey numbers
- Loose Laplacian spectra of random hypergraphs
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- The uniformity lemma for hypergraphs
- Hypergraphs, quasi-randomness, and conditions for regularity
- Quasi‐random classes of hypergraphs
- Constructive lower bounds for off-diagonal Ramsey numbers
- A hypergraph regularity method for generalized Turán problems
- Regularity lemmas for hypergraphs and quasi-randomness
- On codes from hypergraphs.
- High-ordered random walks and generalized Laplacians on hypergraphs
- The finite upper half space and related hypergraphs
- Multicolor Ramsey numbers for complete bipartite versus complete graphs
- Some Ramanujan hypergraphs associated to GL\((n,\mathbb{F}_q)\)
Cited In (24)
- On the first and second eigenvalue of finite and infinite uniform hypergraphs
- Natural quasirandomness properties
- Quasirandomness in hypergraphs
- Quasirandomness in hypergraphs
- Perfect packings in quasirandom hypergraphs. I.
- Quasi-random Boolean functions
- Perfect Packings in Quasirandom Hypergraphs II
- σ-algebras for quasirandom hypergraphs
- Spectra of random regular hypergraphs
- Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
- Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
- Sparse random tensors: concentration, regularization and applications
- Linear quasi-randomness of subsets of abelian groups and hypergraphs
- Linear quasi-randomness of subsets of abelian groups and hypergraphs
- Adjacency spectra of random and complete hypergraphs
- The Erdős-Hajnal hypergraph Ramsey problem
- Principal eigenvectors of general hypergraphs
- Eigenvalues of non-regular linear quasirandom hypergraphs
- Tiling multipartite hypergraphs in quasi-random hypergraphs
- Hamilton cycles in quasirandom hypergraphs
- Forcing quasirandomness with triangles
- Tight Hamilton cycles in cherry-quasirandom 3-uniform hypergraphs
- F$F$‐factors in Quasi‐random Hypergraphs
- Deterministic tensor completion with hypergraph expanders
This page was built for publication: Eigenvalues and linear quasirandom hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496786)
