Expected faces in G(n,p) random embedding logarithmic
Conjecture 1.13 · arXiv:2211.01032
Status open high confidence
Conjecture 1.13 from arXiv:2211.01032 asserts that the expected number of faces in a random embedding of G(n,p) is (1+o(1))ln(pn^2). The authors prove a weaker log-squared upper bound E[F(G(n,p))] <= ln^2(n) + 1/p (Theorem 1.10), and obtain tight Theta(log n) results for bounded-degree random graph models, but the full conjecture for arbitrary G(n,p) remains open. No subsequent paper resolving the conjecture was found in a search of the literature through May 2026.
Reviewer notes. The paper was submitted to arXiv in November 2022 and revised to its current form in April 2025 (SODA 2024 extended abstract). The authors explicitly note that extending their proof technique from complete graphs and bounded-degree models to general G(n,p) 'requires further ideas' and list this as an open problem in Section 9. No follow-up paper resolving the conjecture was found in four web searches; the conjecture is recent and open with high confidence.
Context
In light of the paper's theorems for specific graph families and Monte Carlo experiments, the authors conjecture that a logarithmic bound holds for any usual model of random graphs. Extending the proof of Theorem 1.5 to arbitrary random graphs requires further ideas; Section 9 provides additional discussion.
Also stated in
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