The chain-of-triangles bound for expected faces

Let GG be a simple graph of order nn, and let FF denote the number of faces of a uniformly random orientable embedding of GG. Chain-of-triangles conjecture. For every such graph,

E[F]13n+1.\mathbb{E}[F]\leq \frac{1}{3}n+1.

A chain of triangles connected by cutedges attains E[F]=13n+1\mathbb{E}[F]=\frac{1}{3}n+1, so the conjecture proposes that this construction is extremal. The source first establishes the general upper bound E[F]<π26n\mathbb{E}[F]<\frac{\pi^2}{6}n for simple graphs, leaving the sharper constant conjectured here.

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.