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))/n^4 = 5/32 as n approaches infinity.

[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.