Quasi-random hypergraphs and spanning subhypergraph containment
Structural and extremal properties of graphs and hypergraphs
Ramsey and anti-Ramsey structures in deterministic and random graphs
| Full text | |
| Author(s): |
Total Authors: 4
|
| Affiliation: | [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
Total Affiliations: 4
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 100, n. 2, p. 151-160, MAR 2010. |
| Web of Science Citations: | 23 |
| Abstract | |
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) | |
| FAPESP's process: | 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | PRONEX Research - Thematic Grants |