Premium
K 5 ‐free subgraphs of random graphs
Author(s) -
Gerke S.,
Schickinger T.,
Steger A.
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20000
Subject(s) - combinatorics , mathematics , conjecture , random regular graph , graph , lemma (botany) , discrete mathematics , random graph , chordal graph , 1 planar graph , ecology , poaceae , biology
Abstract We consider a conjecture by Kohayakawa, Łuczak, and Rödl, which, if true, would allow the application of Szemerédi's regularity lemma to show Turán‐type results for all random graphs and any fixed graph H . We deal with 5‐partite graphs such that each part contains n vertices, and any two parts form an ε‐regular pair with m edges. Here, two sets of vertices U and W of size n form an ε‐regular pair with m edges if all subsets U ′ ⊆ U and W ′ ⊆ W with | U ′|, | W ′| ≥ ε n satisfy || E ( U ′, W ′)| − | U ′| | W ′| m / n 2 | ≤ ε| U ′| | W ′| m / n 2 . We show that for each β > 0, there exists at most β m ( m n 2) 10 such graphs that do not contain a K 5 as a subgraph if m ≥ Cn 5/3 for a constant C = C (β), ε is sufficiently small, and n is sufficiently large. This proves the special case of the conjecture when H equals the complete graph on five vertices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004