Kₘ extremal threshold in H-free G(n,p)

Motivating Question (Introduction) · arXiv:1612.09143

arXiv Question medium confidence— first stated 2017-11-19

Authors: Noga Alon, Alexandr Kostochka, Clara Shikhelman

Status partial high confidence

The source paper resolves the question when $m_2(H) \geq m_2(K_m)$ (Theorem 1.2) but only partially when $m_2(H) < m_2(K_m)$ (Theorem 1.4), leaving the exact transition threshold in the harder regime open. Samotij and Shikhelman (arXiv:1806.06609, 2018) generalise the problem to arbitrary pattern graphs $T$ in place of $K_m$: for the case $m_2(H) \leq m_2(T)$ they identify that threshold locations are governed by densities of coverings of $H$ by copies of $T$, reducing the question to deterministic hypergraph Tur\'{a}n problems that remain unsolved in full generality. The full question --- in particular the exact threshold when $m_2(H) < m_2(K_m)$ --- remains open.

Cited literature (1)

partial A generalized Turán problem in random graphs (2018)

Wojciech Samotij, Clara Shikhelman · arXiv preprint · arXiv:1806.06609

Extends the threshold analysis to arbitrary pattern graph T (not just K_m) and, for the harder case m_2(H) ≤ m_2(T), reduces the exact threshold question to deterministic hypergraph Turán problems without resolving them in full generality.

Reviewer notes. Samotij-Shikhelman (1806.06609) is the main verified post-paper follow-up; it makes structural progress on the threshold question but does not settle it in full generality, especially for the regime m_2(H) < m_2(K_m). Morris-Riordan (arXiv:2504.00964, 2025) studies clique distributions in G(n,p) but addresses K_r-factors, not the H-free Turán threshold question.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. For which values of $p$ is it true that $\mathrm{ex}(G(n,p), K_m, H) = (1+o(1))\binom{k-1}{m}\left(\frac{n}{k-1}\right)^m p^{\binom{m}{2}}$ w.h.p.?

Context

For any fixed $H$ with $\chi(H)=k>m$ the deterministic extremal result gives $\mathrm{ex}(n,K_m,H)=(1+o(1))\binom{k-1}{m}(n/(k-1))^m$. Analogous to the edge case characterised by Theorem 1.1, the authors ask for which values of $p$ this extremal count is achieved with high probability in $G(n,p)$. The paper answers the question fully when $m_2(H)\geq m_2(K_m)$ (Theorem 1.2) and only partially when $m_2(H)<m_2(K_m)$ (Theorem 1.4), leaving the exact transition threshold in the latter case open; the paper closes with a dedicated Section 6 of open problems not included in the provided text.

Notes. Posed in introductory prose without a labelled environment. Section 6 (open problems) is absent from the provided PDF extraction, so further explicit open-problem formulations may be missing. PDF source — math may be garbled.

Source paper

Many cliques in $H$-free subgraphs of random graphs
Noga Alon, Alexandr Kostochka, Clara Shikhelman · 2017-11-19
https://arxiv.org/abs/1612.09143 PDF source