Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649639 | Discrete Mathematics | 2009 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vladimir Nikiforov,