Weak hypergraph regularity and linear hypergraphs

We consider conditions which allow the embedding of linear hypergraphs of fixed size. In particular, we prove that any k-uniform hypergraph H of positive uniform density contains all linear k-uniform hypergraphs of a given size. More precisely, we show that for all integers l >= k >= 2 and every d > 0 there exists Q > 0 for which the following holds: if His a sufficiently large k-uniform hypergraph with the property that the density of H induced on every vertex subset of size on is at least d, then H contains every linear k-uniform hypergraph F with l vertices. The main ingredient in the proof of this result is a counting lemma for linear hypergraphs, which establishes that the straightforward extension of graph epsilon-regularity to hypergraphs suffices for counting linear hypergraphs. We also consider some related problems. (C) 2009 Elsevier Inc. All rights reserved.

FAPESP[FAPESP 2003/09925-5]

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[308509/2007-2]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[485671/2007-7]

CNPq[486124/2007-0]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

NSF[DMS 0639839]

NSF

NSF

NSF[DMS 0300529]

NSF

NSF[DMS 0800070]