Expected faces logarithmic for all G(n,p)

Conjecture 9.1 · arXiv:2211.01032

arXiv Conjecture high confidence— first stated 2025-04-09

Authors: Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar, Robert Šámal

Status open high confidence

Conjecture 9.1 from arXiv:2211.01032 asserts that for any density function p(n), almost all graphs in G(n,p) have E[F] = O(log n). The paper itself proves this for dense graphs (p >= 1/polylog n, Corollary 7.3, polylogarithmic bound) and for sparse random graphs (Section 8, logarithmic bound), leaving the general case open. The conjecture would follow from the stronger Conjecture 1.13. No subsequent work resolving the full conjecture was found in the literature.

Reviewer notes. No follow-up paper resolving Conjecture 9.1 was found. The paper's latest revision (v3, April 2025) still lists the conjecture as open. Conjecture 9.1 is a consequence of the stronger Conjecture 1.13 (also open), which predicts E[F] = (1+o(1)) ln(pn^2) for G(n,p).

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

Conjecture. For any $p(n) : \mathbb{N} \rightarrow [0,1]$, almost all graphs in $G(n,p)$ satisfy $\mathbb{E}[F] = O(\log(n))$.

Context

Corollary 7.3 establishes a polylogarithmic bound for almost all dense graphs (when $p \geq 1/\mathrm{polylog}\, n$), and Section 8 gives a logarithmic bound for random sparse graphs. The authors conjecture that the logarithmic property holds without any density condition on edges. This conjecture would follow from the stronger Conjecture 1.13.

Source paper

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar, Robert Šámal · 2025-04-09
https://arxiv.org/abs/2211.01032