The random embedding edge-type conjecture for bridgeless cubic graphs

The random-embedding edge-type conjecture fails for the tetrahedron

Babak Ghanbari and Robert Šámal conjecture in Conjecture 1 of Facial diagrams and cycle double cover that, for a random embedding of every bridgeless cubic graph with $m$ edges, the expected numbers of bad singular, good singular and regular edges all equal $m/3$.

The paper does not spell out the probability law in its conjecture. However, Šámal explicitly defines the intended random-embedding distribution in his conference abstract Random embeddings of graphs, page 27: the local cyclic rotations are chosen uniformly and independently, and in the nonorientable setting the edge signs are also chosen independently at random. Since good singular edges cannot occur in orientable embeddings, the conjecture necessarily concerns this signed, arbitrary-surface distribution. We use exactly that distribution throughout.

1. A general arithmetic obstruction

Let $G$ be a cubic graph with $v$ vertices and $m$ edges. At each vertex there are exactly two cyclic orders of its three incident edges, and every edge has two possible signs. Therefore the uniform signed-rotation distribution has

$$|\Omega(G)|=2^{v+m} \tag{1}$$

equiprobable outcomes. For a fixed edge $e$ and any one of the three facial types $T$, its occurrence probability consequently has the form

$$\mathbb P(e\text{ has type }T) =\frac{a_{e,T}}{2^{v+m}}, \qquad a_{e,T}\in\mathbb Z_{\geq0}. \tag{2}$$

Suppose now that $G$ is edge-transitive. Every automorphism of $G$ induces a probability-preserving permutation of $\Omega(G)$ and preserves the three facial types. Hence (2) is independent of the chosen edge; write the common probability as $p_T$. If $X_T$ denotes the number of type-$T$ edges, linearity of expectation gives

$$\mathbb E[X_T]=m p_T. \tag{3}$$

The conjectured equality $\mathbb E[X_T]=m/3$ would therefore imply

$$p_T=\frac13. \tag{4}$$

But (2) and (4) together require

$$3a_{e,T}=2^{v+m}, \tag{5}$$

which is impossible. Thus none of the three conjectured expectations can hold for any edge-transitive cubic graph under the stated random-embedding distribution.

In particular, the complete graph

$$G=K_4 \tag{6}$$

is simple, cubic, bridgeless and edge-transitive. It has $v=4$ and $m=6$, so the conjecture predicts that each of the three expected counts equals $2$. Equation (5) already proves that every one of these three predictions is false.

2. The exact three expectations for $K_4$

For completeness, the three incorrect predictions admit a short exact census. Label the vertices $0,1,2,3$ and order the six edges as

$$01,02,03,12,13,23. \tag{7}$$

Choose at each vertex the cyclic order induced by increasing neighboring labels. Every other local rotation differs by reversing the order at a subset of vertices. Reversing the local orientation at a vertex and simultaneously changing the signs of its three incident edges preserves the embedded ribbon graph and all of its facial edge types. Consequently, each of the

$$2^4\cdot2^6=1024 \tag{8}$$

uniform signed rotation systems has exactly one equivalent representative with the fixed chosen rotations, and each such representative occurs with multiplicity $2^4$. It therefore suffices to give equal weight to the

$$2^6=64 \tag{9}$$

edge-sign assignments for the fixed rotations.

Here is a purely mathematical facial-walk description of the census. A flag is a triple $(v,e,s)$, where $v$ is incident to $e$ and $s\in\{0,1\}$ specifies the side of the edge ribbon. Write $\rho_v$ for the fixed cyclic order at $v$, and encode the sign of an edge by $\varepsilon_e\in\{0,1\}$. Define the two flag involutions

$$A(v,e,s)=(w,e,s\mathbin{\oplus}1\mathbin{\oplus}\varepsilon_e), \qquad e=vw, \tag{10}$$

and

$$\begin{aligned} B(v,e,1)&=(v,\rho_v(e),0),\\ B(v,e,0)&=(v,\rho_v^{-1}(e),1). \end{aligned} \tag{11}$$

The orbits of the group generated by $A$ and $B$ are precisely the facial boundary components. For an edge $e=vw$, let

$$f_0=(v,e,0), \qquad f_1=(v,e,1). \tag{12}$$

Then $e$ is regular precisely when $f_0$ and $f_1$ lie in different facial boundary components. If they lie in the same component, the cycles of $BA$ distinguish the directions of its two occurrences:

$$\begin{array}{c|c} \text{condition}&\text{type of }e\\ f_0,f_1\text{ in different }\langle A,B\rangle\text{-orbits} &\text{regular}\\ f_0,f_1\text{ in the same }BA\text{-orbit} &\text{good singular}\\ f_0,f_1\text{ in the same }\langle A,B\rangle\text{-orbit but different }BA\text{-orbits} &\text{bad singular}. \end{array} \tag{13}$$

Indeed, the second line means that the two occurrences traverse $e$ in the same direction, while the third means that they traverse it in opposite directions, exactly as in the source's definitions.

For each of the 64 sign assignments, let $(b,g,r)$ record its numbers of bad singular, good singular and regular edges. The complete profile distribution obtained from (10)–(13) is

$$\begin{array}{c|c|c|c} b&g&r&\text{number of sign assignments}\\ 0&0&6&2\\ 0&1&5&6\\ 0&2&4&3\\ 1&1&4&6\\ 1&2&3&12\\ 2&0&4&3\\ 2&4&0&12\\ 3&0&3&4\\ 3&3&0&16. \end{array} \tag{14}$$

The multiplicities sum to $64$, and every row satisfies $b+g+r=6$. Summing each edge-type column against its multiplicity gives

$$\sum b=108, \qquad \sum g=138, \qquad \sum r=138. \tag{15}$$

Therefore the actual expectations are

$$\boxed{ \mathbb E[X_{\mathrm{bad}}]=\frac{27}{16}, \qquad \mathbb E[X_{\mathrm{good}}]=\frac{69}{32}, \qquad \mathbb E[X_{\mathrm{regular}}]=\frac{69}{32}. } \tag{16}$$

All three values differ from the conjectured $m/3=2$. Thus the tetrahedron simultaneously contradicts every clause of Conjecture 1 under the random signed-embedding distribution explicitly specified by its coauthor.