The multigraph linear-logarithmic expected-face conjecture

Let GG be an nn-vertex multigraph with maximum edge-multiplicity μ\mu. Select an orientable embedding of GG uniformly at random, and let FF denote its number of faces. Multigraph expected-face conjecture. The expected number of faces satisfies

E[F]=O(nlog(2μ)).\mathbb{E}[F]=O\bigl(n\log(2\mu)\bigr).

This generalizes the simple-graph conjecture to multigraphs with parallel edges of bounded maximum multiplicity. The source states that this more general conjecture is treated, but the supplied text gives no resolution status.

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

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.