The linear expected-face conjecture for random orientable embeddings
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.