Paper Info
Title
On k-partite hypergraphs with the induced epsilon-density property
Abstract
In this paper we extend the study of bipartite graphs with the induced ε-density property introduced by Frankl, Rödl, and the author. For a given k-partite k-uniform hypergraph G we say that a k-partite k-uniform hypergraph R=(W1,…,Wk,F) has the induced ε-density property if every subhypergraph of R with at least ε|F| edges contains a copy of G which is an induced subhypergraph of R. We show that for every ε>0 and positive integers k and n there exists a k-partite k-uniform hypergraph R with the induced ε-density property for every G=(V1,…,Vk,E) with |V1|,…,|Vk|≤n. We give several proofs of this result, some of which allow for the hypergraph R to be taken with at most 22cnk−1 vertices.
Year
DOI
Venue
2010
10.1016/j.disc.2010.01.010
Discrete Mathematics
Keywords
DocType
Volume
Ramsey type problems,Hypergraphs,Density property
Journal
310
Issue
ISSN
Citations 
10
0012-365X
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Andrzej Dudek111423.10