The chain-of-triangles bound for expected faces
The chain-of-triangles bound for expected faces
Let be a simple graph of order , and let denote the number of faces of a uniformly random orientable embedding of . Chain-of-triangles conjecture. For every such graph,
A chain of triangles connected by cutedges attains , so the conjecture proposes that this construction is extremal. The source first establishes the general upper bound 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.