The quasi-randomness of hypergraph cut properties
From MaRDI portal
Abstract: Let a_1,...,a_k satisfy a_1+...+a_k=1 and suppose a k-uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets A_1,...,A_k of sizes a_1*n,...,a_k*n, the number of edges intersecting A_1,...,A_k is the number one would expect to find in a random k-uniform hypergraph. Can we then infer that H is quasi-random? We show that the answer is negative if and only if a_1=...=a_k=1/k. This resolves an open problem raised in 1991 by Chung and Graham [J. AMS '91]. While hypergraphs satisfying the property corresponding to a_1=...=a_k=1/k are not necessarily quasi-random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi-random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes.
Recommendations
- Quasi-randomness of graph balanced cut properties
- Quasirandomness in hypergraphs
- Quasirandomness in hypergraphs
- On the maximal cut in a random hypergraph
- Quasi-randomness and the regularity method in hypergraphs
- Hypergraph regularity and quasi-randomness
- scientific article; zbMATH DE number 747030
- Hypergraphs, quasi-randomness, and conditions for regularity
- Quasi-random hypergraphs revisited
Cites work
- A Certain Class of Incidence Matrices
- A variant of the hypergraph removal lemma
- Extremal problems on set systems
- Generalized quasirandom graphs
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
- Hereditary quasi-random properties of hypergraphs
- scientific article; zbMATH DE number 4027516 (Why is no real title available?)
- scientific article; zbMATH DE number 3523693 (Why is no real title available?)
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Quasi-random graphs
- Quasi-random hypergraphs
- Quasi-Random Set Systems
- Quasi-random tournaments
- Quasi-randomness and the distribution of copies of a fixed graph
- Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
- Quasirandom Groups
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Quick approximation to matrices and applications
- Regularity Lemma for k-uniform hypergraphs
- Szemerédi's lemma for the analyst
- The counting lemma for regular k‐uniform hypergraphs
- Weak hypergraph regularity and linear hypergraphs
- Weak quasi-randomness for uniform hypergraphs
Cited in
(16)- More on quasi-random graphs, subgraph counts and graph limits
- Quasi-random oriented graphs
- Quasi-randomness of graph balanced cut properties
- σ-algebras for quasirandom hypergraphs
- A theorem on incidence matrices and quasirandom hypergraphs
- Weak quasi-randomness for uniform hypergraphs
- Rational decomposition of dense hypergraphs and some related eigenvalue estimates
- Forcing quasirandomness with triangles
- scientific article; zbMATH DE number 747030 (Why is no real title available?)
- The poset of hypergraph quasirandomness
- Perfect Packings in Quasirandom Hypergraphs II
- Eigenvalues and linear quasirandom hypergraphs
- Linear quasi-randomness of subsets of abelian groups and hypergraphs
- Linear quasi-randomness of subsets of abelian groups and hypergraphs
- FF‐factors in Quasi‐random Hypergraphs
- Steiner triple systems with high discrepancy
This page was built for publication: The quasi-randomness of hypergraph cut properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3119045)
