ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.