Non-orientable embedding faces below orientable

Conjecture 9.6 · 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.6 asserts that the expected face count under a uniformly random non-orientable embedding never exceeds the expected face count under a uniformly random orientable embedding, for any graph G. No paper resolving or making substantial progress on this specific conjecture was found in the indexed literature. The conjecture is verified in the source paper only for toy cases (dipole, chains of triangles joined by cut edges), and the bound E[F^-] <= (1/2)E[F] + 1 is established for the dipole via Random Process A.

Reviewer notes. No follow-up found after 4 web searches. The conjecture is recent (source paper first posted November 2022, published at SODA 2024, revised April 2025). Absence of follow-up is expected for a conjecture of this vintage in a specialized topological graph theory setting.

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

Conjecture. Let $F^{-}$ be the random variable for the average number of faces in a non-orientable random embedding of some graph $G$. Then $\mathbb{E}[F^{-}] \leq \mathbb{E}[F]$.

Context

The authors conjecture that the expected face count in a non-orientable random embedding is always at most that of the orientable random embedding, for any graph $G$. The inequality is verified for toy models (including the dipole and chains of triangles joined by cut edges), and an analysis of Random Process A gives the bound $\mathbb{E}[F^{-}] \leq \frac{1}{2}\mathbb{E}[F] + 1$ for the dipole.

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