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.

[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