Linear face bound in random graph embeddings
Conjecture 4 · arXiv:2202.07746
Status open high confidence
No follow-up paper proving or disproving Conjecture 4 (E[F] \leq \frac{1}{3}n + 1 for simple graphs) has been found. The source paper itself establishes E[F] \leq \frac{\pi^2}{6}n (Theorem 8) and notes that a chain of triangles connected by cut edges achieves E[F] = \frac{1}{3}n + 1, making this the conjectured tight constant. A related follow-up (arXiv:2211.01032, SODA 2024) by Campion Loth, Halasz, Masarik, Mohar, and Samal proves logarithmic expected face counts for many specific graph families (complete graphs, random graphs, degree-bounded models), but does not address the worst-case tight linear conjecture.
Reviewer notes. The conjecture is recent (journal published 2023) and a wide search found no follow-up addressing the tight constant 1/3. The related paper arXiv:2211.01032 (SODA 2024, by partially overlapping authors) shows logarithmic bounds for most graphs but does not address this specific extremal conjecture. Absence of evidence is not suspicious given the difficulty of improving worst-case linear constants in random embedding theory.
Context
The paper proves $E[F] \leq \frac{\pi^2}{6}n$ for simple graphs (Theorem 8), but no examples approaching this constant are known. A chain of triangles connected by cut edges achieves $E[F] = \frac{1}{3}n+1$, which the authors conjecture is the true optimal bound.
Notes. PDF source; fraction $\frac{1}{3}$ appears as '1\n3' in raw PDF text but context is unambiguous.
Source paper
Expected number of faces in a random embedding of any graph is at most linear
Jesse Campion Loth, Bojan Mohar · 2023-03-30
https://arxiv.org/abs/2202.07746
PDF source