Weak quasi‐randomness for uniform hypergraphs |
| |
| Authors: | David Conlon Hiêp Hàn Yury Person Mathias Schacht |
| |
| Institution: | 1. St John's College, Cambridge, CB2 1TP, UKSupported by a Junior Research Fellowship at St John's College, Cambridge.;2. Instituto de Matemática e Estatística, Universidade de S?o Paulo, 05508‐090 S?o Paulo, BrazilSupported by DFG within the research training group “Methods for Discrete Structures”.;3. Institut für Mathematik, Freie Universit?t Berlin, Arnimallee 3, D‐14195 Berlin, GermanySupported by GIF (I‐889‐182.6/2005).;4. Fachbereich Mathematik, Universit?t Hamburg, Bundesstra?e 55, D‐20146 Hamburg, Germany |
| |
| 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., 2011 |
| |
| Keywords: | hypergraphs quasi‐randomness regularity lemma forcing conjecture for graphs |
|
|
