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

Noga Alon, Alexandr Kostochka, Clara ShikhelmanJournal of Combinatorics 2018 · DOI · arXiv

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) > m$, the behavior of $ex(G(n,p),K_m,H)$ depends strongly on the relation between $p$ and the 2-density $m_2(H)$. 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 $(\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) < m_2(K_m)$, we show that the transition occurs at a value of $p$ significantly larger than $n^{-1/m_2(H)}$. To support these findings, we construct a family of $k$-chromatic graphs with minimal 2-density, which may be of independent interest.

Introduction

In classical extremal graph theory, the Turán function $ex(n, H)$ determines the maximum number of edges an $n$-vertex graph can contain without including $H$ as a subgraph. A sophisticated extension of this problem involves studying these extremal properties within the context of a random graph $G(n, p)$, where each edge exists independently with probability $p$.

This paper investigates a generalized version of this problem: instead of counting edges (which are $K_2$ cliques), we seek the maximum number of larger cliques ($K_m$) that can exist in a subgraph of $G(n, p)$ that remains $H$-free. This value, denoted as $ex(G(n, p), K_m, H)$, exhibits a fascinating phase transition as the edge probability $p$ varies, dictated by the structural density of the forbidden graph $H$.

The 2-Density Threshold

The core of the analysis revolves around the 2-density of the forbidden graph $H$, defined as: $$m_2(H) = \max_{H' \subseteq H, v(H') \geq 3} \left\{ \frac{e(H')-1}{v(H')-2} \right\}$$

This parameter serves as a measure of the "densest" part of $H$. The research reveals that the relationship between $m_2(H)$ and the 2-density of the clique $K_m$ determines the nature of the phase transition.

Case 1: The Dense Regime ($m_2(H) \geq m_2(K_m)$)

When $H$ is at least as dense as the clique we are trying to preserve, Theorem 1.2 establishes a sharp transition at the threshold $p = n^{-1/m_2(H)}$:

  • Below the threshold: The random graph is sparse enough that one can keep almost all copies of $K_m$ found in $G(n, p)$ while still avoiding $H$.
  • Above the threshold: The density of $H$ copies becomes overwhelming. The optimal strategy shifts to selecting a $(\chi(H)-1)$-partite subgraph of $G(n, p)$, which necessarily discards a significant fraction of the cliques but guarantees the absence of $H$.

Case 2: The Sparse Regime ($m_2(H) < m_2(K_m)$)

If $H$ is sparser than $K_m$, Theorem 1.4 demonstrates that the transition is "delayed." Even when $p$ exceeds $n^{-1/m_2(H)}$, one can typically still retain most of the $K_m$ copies. In this regime, edges are statistically more likely to contribute to the formation of $K_m$ cliques than to the formation of the forbidden graph $H$, allowing for a higher density of cliques before the $H$-free constraint forces a structural change.

Methodological Framework

The authors utilize several advanced techniques to bridge the gap between sparse random graphs and dense extremal theory:

  1. Sparse Regularity and Counting: The Kohayakawa-Rödl sparse regularity lemma is employed to handle the regime where $p$ is relatively large, allowing the random graph to be treated with tools similar to those used in dense graph theory.
  2. Probabilistic Method: Concentration inequalities (such as Chernoff and Markov) are used to prove that the number of cliques in the random graph remains close to its expected value with high probability.
  3. Hierarchical Construction: To prove the existence of $k$-chromatic graphs with specific 2-densities, the authors introduce a construction involving "towers," "complexes," and "supercomplexes."

Minimal 2-Density Construction

A significant contribution of this work is the construction of a family of $k$-chromatic graphs $G(k, \epsilon_i)$ where the 2-density tends toward the theoretical minimum: $$\lim_{i \to \infty} m_2(G(k, \epsilon_i)) = \frac{(k+1)(k-2)}{2(k-1)}$$

This result (Theorem 1.3) is tight for all $k \geq 4$ and ensures that the "Sparse Case" described in the paper is not merely a theoretical curiosity but applies to a broad class of graphs.

Conclusion and Future Directions

While this paper characterizes the phase transition for $K_m$ in $H$-free subgraphs, the exact threshold for the sparse $H$ case remains an open question. The authors conjecture that the critical value of $p$ is linked to the probability that a random edge in $G(n, p)$ is contained within a copy of $K_m$. Future research may also extend these results beyond cliques to other fixed target graphs $T$, such as cycles or complete bipartite graphs.

Summary updated

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 $χ(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'\subset H, |V(H')|'\geq 3}\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 $χ(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 $δ&gt;0$ small at $p=n^{-1/m_2(H)+δ}$ 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 \geq 4$ we construct a family of $k$ chromatic graphs $G(k,ε_i)$ where $m_2(G(k,ε_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$
BibTeX
@article{alon2018many,
  author = {Noga Alon and Alexandr Kostochka and Clara Shikhelman},
  title = {{Many cliques in $H$-free subgraphs of random graphs}},
  journal = {Journal of Combinatorics},
  year = {2018},
  doi = {10.4310/joc.2018.v9.n4.a1},
}

Loading related content...

Figure