Weak quasi‐randomness for uniform hypergraphs
- 10 November 2011
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 40 (1) , 1-38
Abstract
We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs.Moreover, let Kk be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (Kk,M(k)) has the property that if the number of copies of both Kk and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011Keywords
This publication has 30 references indexed in Scilit:
- Hereditary quasirandom properties of hypergraphsCombinatorica, 2011
- Quasi-randomness and the distribution of copies of a fixed graphCombinatorica, 2008
- Regularity Lemma for k‐uniform hypergraphsRandom Structures & Algorithms, 2004
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphsCombinatorica, 1997
- The Algorithmic Aspects of the Regularity LemmaJournal of Algorithms, 1994
- Cohomological Aspects of HypergraphsTransactions of the American Mathematical Society, 1992
- Regularity lemmas for hypergraphs and quasi‐randomnessRandom Structures & Algorithms, 1991
- Quasi-random set systemsJournal of the American Mathematical Society, 1991
- Quasi‐random classes of hypergraphsRandom Structures & Algorithms, 1990
- On a Packing and Covering ProblemEuropean Journal of Combinatorics, 1985