K 5 ‐free subgraphs of random graphs

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