Random Structures and Algorithms · 2011 · 63 citations · 28 references
Natural SciencesMathematicsCombinatoricsDiscrete MathematicsProbability TheoryGraph TheoryHypergraph TheoryProbabilistic CombinatoricsDensityRandom Graph TheoryUniform Hypergraphs
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 K k 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 ( K k , M ( k )) has the property that if the number of copies of both K k 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., 2011
28
Endre Szemerédi · Defense Technical Information Center (DTIC) · 1975 · 806 citations
Fan Chung, Ronald Graham, R. Wilson · COMBINATORICA · 1989 · 486 citations
On a Packing and Covering Problem
Vojtěch Rödl · European Journal of Combinatorics · 1985 · 414 citations
The Algorithmic Aspects of the Regularity Lemma
Noga Alon, Richard A. Duke, Hanno Lefmann et al. · Journal of Algorithms · 1994 · 322 citations