Weak hypergraph regularity and linear hypergraphs

Autor(es)

Kohayakawa, Yoshiharu ^[1] ; Nagle, Brendan ^[2] ; Rodl, Vojtech ^[3] ; Schacht, Mathias ^[4]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estatistica, BR-05508090 Sao Paulo - Brazil

^[2] Univ S Florida, Dept Math & Stat, Tampa, FL 33620 - USA

^[3] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 - USA

^[4] Humboldt Univ, Inst Informat, D-10099 Berlin - Germany

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 100, n. 2, p. 151-160, MAR 2010.
• Citações Web of Science: 23

Resumo

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. (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático