The largest $K_r$-free set of vertices in a random graph

Abstract

For $r\ge 2$ and a graph $G$, let ${\alpha }_r(G)$ be the maximum number of vertices in a $K_r$-free subgraph of $G$. We investigate the value ${\alpha }_r(G)$ when $G$ is the random graph $G\sim G_{n,1/2}$ and discover the following phenomenon: with high probability, ${\alpha }_r(G)$ lies in an interval of constant length that varies in a non-monotonic fashion from $1$ to $\lfloor r/2\rfloor +1$ depending on the value of $n$. The special case $r=2$ corresponds to the independence number of random graphs which is well-known to have two-point concentration; our results therefore extend and generalize this basic fact in random graph theory, showing more complicated behavior when $r>2$. We also prove similar results where $K_r$ is replaced by any color critical graph like $C_5$.

30 pages, 2 figures