Many cliques in H-free subgraphs of random graphs

Publication date 10 December 2018

Abstract: For two fixed graphs

T

and

H

let

e x (G (n, p), T, H)

be the random variable counting the maximum number of copies of

T

in an

H

-free subgraph of the random graph

G (n, p)

. We show that for the case

T = K_{m}

and

c h i (H) > m

the behavior of

e x (G (n, p), K_{m}, H)

depends strongly on the relation between

p

and

m_{2} (H) = m a x_{H^{'} s u b s e t H, | V (H^{'}) |^{'} g e q 3} l e f t f r a c e (H^{'}) - 1 v (H^{'}) - 2 i g h t

. When

m_{2} (H) > m_{2} (K_{m})

we prove that with high probability, depending on the value of

p

, either one can maintain almost all copies of

K_{m}

, or it is asymptotically best to take a

c h i (H) - 1

partite subgraph of

G (n, p)

. The transition between these two behaviors occurs at

p = n^{- 1 / m_{2} (H)}

. When

m_{2} (H) < m_{2} (K_{m})

we show that the above cases still exist, however for

d e l t a > 0

small at

p = n^{- 1 / m_{2} (H) + d e l t a}

one can typically still keep most of the copies of

K_{m}

in an

H

-free subgraph of

G (n, p)

. Thus, the transition between the two behaviors in this case occurs at some

p

significantly bigger than

n^{- 1 / m_{2} (H)}

. To show that the second case is not redundant we present a construction which may be of independent interest. For each

k g e q 4

we construct a family of

k

chromatic graphs

G (k, e p s i l o n_{i})

where

m_{2} (G (k, e p s i l o n_{i}))

tends to

f r a c (k + 1) (k - 2) 2 (k - 1) (< m_{2} (K_{k - 1}))

as

i

tends to infinity. This is tight for all values of

k

Recommendations

Cited in

(11)

This page was built for publication: Many cliques in \(H\)-free subgraphs of random graphs