The linear expected-face conjecture for random orientable embeddings

About 4 years old · traced to

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]≤nlog⁡n\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.

References

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.