Logarithmic expected faces in dense graphs

Conjecture 9.3 · 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.3 from arXiv:2211.01032 states that every graph on n vertices with minimum degree Omega(n) satisfies E[F] = Theta(log n) in a random embedding. The source paper confirms this for the complete graph K_n via Theorem 1.8, establishing (1/2)ln(n) - 2 < E[F(K_n)] <= 3.65 ln(n) + o(1). The general case for all dense graphs remains open; a thorough search of the literature found no follow-up paper resolving or substantially advancing the conjecture beyond what is proved in the source paper itself.

Reviewer notes. Theorem 1.8 of the source paper itself confirms the conjecture for K_n. No follow-up paper extending this to general graphs with minimum degree Omega(n) was found after four web searches. The conjecture was stated in the final published version (April 2025), so its open status with high confidence is expected.

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

Conjecture. Let $G$ be a graph on $n$ vertices with minimum vertex degree $\Omega(n)$. Then $G$ satisfies $\mathbb{E}[F] = \Theta(\log(n))$.

Context

Families of sparse graphs with maximum degree $O(1)$ achieving $\mathbb{E}[F] = \Theta(n)$ are known, but no dense graph example with that many average faces has been found. Theorem 1.8 confirms this conjecture for the complete graph $K_n$; the general dense case remains open.

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