The linear expected-face conjecture for random orientable embeddings
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.