The linear expected-face conjecture for multigraphs

Let GG be a multigraph on nn vertices, and let μ\mu be its maximum edge-multiplicity. Choose an orientable embedding of GG uniformly at random. Linear multigraph expected-face conjecture. The expected number of faces is

O(nlog(2μ)).O\bigl(n\log(2\mu)\bigr).

This adjusts the simple-graph conjecture to account for parallel edges. The paper presents it after proving bounds for simple graphs and does not establish it in full; its status is open.

Sources & referencesView supporting material

Primary source

Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar and Robert Šámal, “Random 2-cell embeddings of multistars”, arXiv:2103.05036 (2021).

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.