The linear expected-face conjecture for random orientable embeddings
Let be a simple graph of order . Select an orientable embedding of uniformly at random, and let denote its number of faces. Linear expected-face conjecture. The expected number of faces satisfies
Stahl proved the upper bound , while many bounded-degree graph families with linearly many short cycles have . 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
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.