p(n) range for hereditary subgraph concentration

Open Problem (characterizing edge probabilities for Theorem 1.1) · arXiv:2210.12754

arXiv Problem medium confidence— first stated 2022-10-23

Authors: Noga Alon, Michael Krivelevich, Wojciech Samotij

Status open medium confidence

The source paper proves Theorem 1.1 for fixed p ∈ (0,1) and for p = p(n) satisfying n^{−c} ≤ p ≤ 1−n^{−c}, but the full characterization of all p = p(n) for which the conclusion holds remains open. A 2024 follow-up (arXiv:2405.09486) explicitly addresses a question of Alon, Krivelevich and Samotij in the hereditary setting but still restricts its main results to fixed p ∈ (0,1), leaving the variable-probability regime unresolved.

Cited literature (1)

partial Subgraphs of random graphs in hereditary families (2024)

not verified from abstract · arXiv preprint · arXiv:2405.09486

Explicitly addresses a question of Alon, Krivelevich and Samotij about subgraphs in hereditary families, but its stated results remain in the regime of fixed p ∈ (0,1) rather than characterizing all p = p(n).

Reviewer notes. No paper found that resolves the full characterization of all p = p(n). arXiv:2405.09486 (2024) is the closest follow-up, explicitly citing the question of Alon-Krivelevich-Samotij, but its results are for fixed p. A related paper arXiv:2405.05902 (Fox, Nenadov, Pham; Combinatorica 2025, 'The Largest Subgraph Without A Forbidden Induced Subgraph') generalizes the framework to pseudorandom/quasirandom host graphs, but it was found via search only and not fully verified via WebFetch so is excluded from since_posted. The conjecture is open with medium confidence because active follow-up work exists but the specific p = p(n) characterization problem appears unaddressed.

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

Problem. Characterize all edge probabilities $p = p(n)$ for which the assertion of Theorem 1.1 holds.

Context

Theorem 1.1 is proved for fixed $p \in (0,1)$ and (via Proposition 2.1) for $p = p(n)$ satisfying $n^{-c} \leq p \leq 1-n^{-c}$. The authors note that hereditary (even monotone) properties exist for which the fraction of edges of $G(n,p)$ lying in a maximum in-$\mathcal{P}$ subgraph changes, whp, several times as $p$ increases from 0 to 1.

Notes. PDF source; stated as an informal open problem in the concluding remarks without a labelled environment.

Source paper

Largest subgraph from a hereditary property in a random graph
Noga Alon, Michael Krivelevich, Wojciech Samotij · 2022-10-23
https://arxiv.org/abs/2210.12754 PDF source