Journal of Combinatorics

Volume 9 (2018)

Number 4

Many cliques in $H$-free subgraphs of random graphs

Pages: 567 – 597

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n4.a1

Authors

Noga Alon (Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel; and CMSA, Harvard University, Cambridge, Massachusetts, U.S.A.)

Alexandr Kostochka (Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Il., U.S.A.; and Sobolev Institute of Mathematics, Novosibirsk, Russia)

Clara Shikhelman (Sackler School of Mathematics, Tel Aviv University, Tel Aviv, Israel)

Abstract

For two fixed graphs $T$ and $H$ let $ex(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 $ \chi(H) \gt m$ the behavior of $ex(G(n,p),K_m,H)$ depends strongly on the relation between $p$ and $m_2(H)= \max_{H' \subseteq H, |V(H')|' \geq3} \left \{ \frac{e(H')-1}{v(H')-2} \right \}$.

When $m_2(H) \gt 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 $ \chi(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) \lt m_2(K_m)$ we show that the above cases still exist, however for $ \delta \gt 0$ small at $p=n^{-1/m_2(H)+ \delta}$ 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 \geq4$ we construct a family of $k$-chromatic graphs $G(k, \epsilon_i)$ where $m_2(G(k, \epsilon_i))$ tends to $ \frac{(k+1)(k-2)}{2(k-1)} \lt m_2(K_{k-1})$ as $i$ tends to infinity. This is tight for all values of $k$ as for any $k$-chromatic graph $G$, $m_2(G) \gt \frac{(k+1)(k-2)}{2(k-1)}$.

Keywords

Turán type problems, random graphs, chromatic number

Received 20 January 2017

Published 7 December 2018