Linear expected faces in random orientable embeddings

Status solved high confidence

Conjecture 1 from arXiv:2103.05036 is fully resolved by Campion Loth and Mohar (2023), who proved that for any $n$-vertex multigraph with maximum edge-multiplicity $\mu$, the expected number of faces satisfies $E[F] \leq n(H_{2\mu}+1)$; for simple graphs this specialises to the conjectured $O(n)$ bound, further sharpened to $E[F] \leq \frac{\pi^2}{6}n$ by the same paper. Subsequent work (arXiv:2211.01032, SODA 2024) shows that for complete graphs and most natural graph families the expectation is in fact $\Theta(\ln n)$, far below the linear upper bound.

Cited literature (2)

• proof Expected number of faces in a random embedding of any graph is at most linear (2023)
  Jesse Campion Loth, Bojan Mohar · Combinatorics, Probability and Computing · arXiv:2202.07746 · doi:10.1017/S096354832300010X

  Proves Conjecture 1 by establishing $E[F] \leq n(H_{2\mu}+1)$ for any multigraph (Theorem 3), which specialises to $O(n)$ for simple graphs and is further sharpened to $E[F] \leq \frac{\pi^2}{6}n$ by Theorem 8.

• partial Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic (2024)
  Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar, Robert Šámal · ACM-SIAM Symposium on Discrete Algorithms (SODA 2024) · arXiv:2211.01032

  Goes beyond the resolved conjecture by proving $E[F(K_n)] = \Theta(\ln n)$ and logarithmic bounds for random graphs $G(n,p)$ and bounded-degree models, showing the O(n) bound is far from tight for most graphs.

Reviewer notes. Conjecture 1 is fully proved by arXiv:2202.07746. The three internal references reduce to two distinct papers (2202.07746 appears twice with fuzz scores 97 and 92). arXiv:2211.01032 strengthens the result considerably by showing logarithmic behaviour for most graphs.

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