The linear expected-face conjecture for random orientable embeddings

Let GG be a simple graph of order nn. Select an orientable embedding of GG uniformly at random, and let FF denote its number of faces. Linear expected-face conjecture. The expected number of faces satisfies

E[F]=O(n).\mathbb{E}[F]=O(n).

Stahl proved the upper bound E[F]nlogn\mathbb{E}[F]\leq n\log n, while many bounded-degree graph families with linearly many short cycles have E[F]=Θ(n)\mathbb{E}[F]=\Theta(n). No examples with superlinear expected numbers of faces are known, so the conjecture asks whether the logarithmic factor can always be removed for simple graphs.

Sources & referencesView supporting material

Primary source

Jesse Campion Loth and Bojan Mohar, “Expected number of faces in a random embedding of any graph is at most linear”, arXiv:2202.07746 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.