The Crossing Number of the Cube

A *drawing* of a graph *G* in the plane allows for edges to cross. The *crossing number* *cr(G)* is the fewest number of pairwise edge crossings taken over all drawings of *G*. The *cube Q_n* is defined recursively by *Q_1 = K_1* and *Q_{n+1} = Q_n* x *K_2*. Equivalently, the cube has vertex set all binary strings of length *n* with edges joining those strings that differ in exactly one spot.

**Problem:** *Find the crossing number of the cube.*

Little is known. The 3-cube *Q_3* is planar, so it has crossing number 0. The 4-cube *Q_4* is isomorphic to the Cartesian product of two 4-cycles and has crossing number 8. No other exact values are known. Madej [M] has given a general construction and shown that *cr(Q_n)* is at most *4^n/6 + smaller order terms*. Sykora and Vrto [SV] have shown a lower bound on *cr(Q_n)* of *4^n/20 + smaller order terms*. Erdos and Guy [EG] conjecture that *lim cr(Q_n)/4^n = 5/32* as *n* approaches infinity.

References:

[EG] P. Erdos and R.K. Guy, Crossing number problems, *Amer. Math. Monthly* **80** (1973) 52-58.

[M] T. Madej, Bounds for the crossing number of the *n*-cube, *J. Graph Theory* **15** (1991) 81-97.

[SV] O. Sykora and I. Vrto, On crossing numbers of hypercubes and cube connected cycles, *BIT* **33** (1993) 232-237.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to *dan.archdeacon@uvm.edu *

August, 1995