Chromatic thresholds in dense random graphs

No author found.

Abstract: The chromatic threshold

d e l t a_{c} h i (H, p)

of a graph

H

with respect to the random graph

G (n, p)

is the infimum over

d > 0

such that the following holds with high probability: the family of

H

-free graphs

G s u b s e t G (n, p)

with minimum degree

d e l t a (G) g e d p n

has bounded chromatic number. The study of the parameter

d e l t a_{c} h i (H) : = d e l t a_{c} h i (H, 1)

was initiated in 1973 by ErdH{o}s and Simonovits, and was recently determined for all graphs

H

. In this paper we show that

d e l t a_{c} h i (H, p) = d e l t a_{c} h i (H)

for all fixed

p i n (0, 1)

, but that typically

d e l t a_{c} h i (H, p) e d e l t a_{c} h i (H)

if

p = o (1)

. We also make significant progress towards determining

d e l t a_{c} h i (H, p)

for all graphs

H

in the range

p = n^{- o (1)}

. In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper.