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:
- 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.
- 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.
- 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