The multigraph linear-logarithmic expected-face conjecture

About 4 years old · traced to

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.

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

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.