Logarithmic face conjecture for Erdős–Rényi random graphs

Counterexample: every fixed subcritical edge density

Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar, and Robert Šámal conjecture that, for an unrestricted edge probability $p=p(n)$,

$$\mathbb E[F(n,p)]=(1+o(1))\log(pn^2). \tag{1}$$

This is Conjecture 1.2 in the published SODA 2024 proceedings and Conjecture 1.13 in the later, expanded arXiv version 3. Both statements allow $p$ to depend on $n$ and impose no lower bound on $np$ or connectivity conditioning.

We show that (1) fails throughout the entire subcritical regime

$$p=\frac{c}{n},\qquad 0<c<1. \tag{2}$$

In particular, these counterexamples have linearly many expected edges and satisfy $pn^2\to\infty$, so the proposed logarithm is positive and divergent.

The source's convention for disconnected embeddings

The expanded source explicitly defines the face count for a disconnected embedded graph with connected components $G_1,\ldots,G_q$ by

$$F(G)=\sum_{i=1}^{q}F(G_i)-q+1. \tag{3}$$

It emphasizes that isolated vertices and, more generally, tree components contribute nothing beyond the single global face. Thus, if $G$ is a forest, then $F(G)=1$.

For an arbitrary orientable cellular embedding of a connected component $G_i$, let $h_i\geq0$ be its genus. Euler's formula gives

$$F(G_i) =2-2h_i-|V(G_i)|+|E(G_i)| =1+\beta(G_i)-2h_i, \tag{4}$$

where

$$\beta(G_i)=|E(G_i)|-|V(G_i)|+1 \tag{5}$$

is its cycle rank. Substitution into (3) yields the exact identity

$$F(G)=1+\beta(G)-2\sum_{i=1}^{q}h_i, \qquad \beta(G)=|E(G)|-|V(G)|+q. \tag{6}$$

Because every connected embedding has at least one face, (3) also gives $F(G)\geq1$. Consequently,

$$1\leq F(G)\leq1+\beta(G). \tag{7}$$

Choose a spanning forest of $G$. Each of the $\beta(G)$ edges outside that forest determines a distinct fundamental simple cycle. If $Z(G)$ denotes the total number of simple cycles in $G$, then

$$\beta(G)\leq Z(G), \qquad 1\leq F(G)\leq1+Z(G). \tag{8}$$

This bound holds for every rotation system, so it remains valid after averaging over both the graph and its random embedding.

Exact cycle estimate

For $G\sim G(n,p)$, the expected number $Z_\ell(G)$ of simple cycles of length $\ell\geq3$ is

$$\mathbb E[Z_\ell(G)] =\frac{(n)_\ell}{2\ell}\,p^\ell, \qquad (n)_\ell=n(n-1)\cdots(n-\ell+1). \tag{9}$$

Therefore, when $p=c/n$ with $0<c<1$ fixed,

$$\begin{aligned} \mathbb E[Z(G)] &=\sum_{\ell=3}^{n}\frac{(n)_\ell}{2\ell} \left(\frac{c}{n}\right)^\ell\\ &\leq\frac12\sum_{\ell=3}^{\infty}\frac{c^\ell}{\ell}\\ &=\frac12\left(-\log(1-c)-c-\frac{c^2}{2}\right). \end{aligned} \tag{10}$$

Combining (8) and (10), uniformly for every $n$, gives

$$1\leq\mathbb E[F(n,c/n)] \leq1+\frac12\left(-\log(1-c)-c-\frac{c^2}{2}\right) =O_c(1). \tag{11}$$

In contrast,

$$\log(pn^2)=\log(cn)\longrightarrow\infty. \tag{12}$$

Thus, in fact,

$$\lim_{n\to\infty} \frac{\mathbb E[F(n,c/n)]}{\log(pn^2)}=0, \tag{13}$$

whereas (1) asserts that this ratio tends to $1$.

For the explicit choice $p=1/(2n)$, the uniform numerical bound is

$$1\leq\mathbb E\!\left[F\!\left(n,\frac1{2n}\right)\right] \leq\frac{11}{16}+\frac{\log2}{2} <\frac{19}{16}, \tag{14}$$

although

$$\mathbb E[|E(G)|] =\binom n2\frac1{2n} =\frac{n-1}{4} \longrightarrow\infty, \qquad \log(pn^2)=\log\!\left(\frac n2\right) \longrightarrow\infty. \tag{15}$$

There is also a regime in which the face expectation has an explicit limit: taking $p=n^{-3/2}$ in (8) and (9) gives

$$1\leq\mathbb E[F(n,n^{-3/2})] \leq1+\frac12\sum_{\ell=3}^{\infty} \frac{n^{-\ell/2}}{\ell} =1+O(n^{-3/2}), \tag{16}$$

while

$$pn^2=\sqrt n\longrightarrow\infty, \qquad \mathbb E[|E(G)|]\sim\frac{\sqrt n}{2}, \qquad \log(pn^2)=\frac12\log n\longrightarrow\infty. \tag{17}$$

Hence the conjecture, as stated without a density restriction, is false. Whether an appropriately restricted version holds in a denser regime is a separate question not resolved here.