Article ID Journal Published Year Pages File Type
4649639 Discrete Mathematics 2009 6 Pages PDF
Abstract

Extending a classical result of Erdős, we derive the following concise statement:Let r≥3r≥3 and (lnn)−1/(r−1)≤α≤r−3(lnn)−1/(r−1)≤α≤r−3. Then every rr-uniform graph on nn vertices with at least αnr/r!αnr/r! edges contains a complete rr-partite subgraph with r−1r−1 classes of size ⌊α(lnn)1/(r−1)⌋⌊α(lnn)1/(r−1)⌋ and one class of size ⌈n1−αr−2⌉⌈n1−αr−2⌉.Our main result is a similar, but stronger statement about directed hypergraphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,