Non-orientable random embedding faces of Kₙ

Conjecture 9.5 · 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.5 from arXiv:2211.01032 posits that the expected number of faces in a non-orientable random embedding of $K_n$ (defined via a random rotation system combined with a random signature assigning each edge a sign independently with probability $1/2$) is at most $\ln(n) + O(1)$. This is the non-orientable analogue of the paper's main theorem for orientable embeddings. The conjecture is supported only by computer simulations reported by the authors; no subsequent work resolving or making partial progress on it has been found in the literature. The conjecture first appeared in the April 2025 (v3) version of the paper, so it is very recent.

Reviewer notes. No follow-up found. The conjecture was introduced in the v3 (April 2025) of the paper, making it at most one year old at review time. All web searches returned only the source paper and its orientable predecessors; no citing paper addressing the non-orientable case was found.

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

Conjecture. The expected number of faces in a non-orientable random embedding of the complete graph $K_{n}$ is at most $\ln(n) + O(1)$.

Context

The authors extend their investigation to non-orientable surfaces, where a random embedding is defined by choosing a random rotation system together with a random signature assigning each edge a sign independently with probability $1/2$. Computer simulations support a logarithmic behaviour analogous to the orientable case.

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