The Crossing Number of the Hypercube

A drawing of a graph G in the plane has the vertices represented by distinct points and the edges represented by polygonal lines joining their endpoints such that:

• no edge contains a vertex other than its endpoints,
• no two adjacent edges share a point other than their common endpoint, 
• two nonadjacent edges share at most one point at which they cross transversally, and
• no three edges cross at the same point.

The crossing number cr(G) of G is the minimum number of crossings in all drawings of G in the plane.

The d-dimensional (hyper)cube Q_d is the graph whose vertices are all binary sequences of length d, and two of the sequences are adjacent in Q_d if they differ in precisely one coordinate.

Conjecture (Erdős and Guy [1]):  lim  cr(Q_d) / 4^d = 5/32 (as n tends to infinity).

It is known that cr(Q_d) = 0 for d = 1,2,3 and that cr(Q₄) = 8. No other exact values are known. Madej [3] proved that cr(Q_d) is at most 4^d/6 + o(4^d/6). Faria and de Figueiredo [2] improved the upper bound to (165/1024) 4^d. Sykora and Vrto [4] proved that 4^d/20 + o(4^d/20) is a lower bound on cr(Q_d). 

References

[1] P. Erdős and R.K. Guy, Crossing number problems, Amer. Math. Monthly 80 (1973) 52-58.

[2] L. Faria, C.M.H. de Figueiredo, On Eggleton and Guy's conjectured upper bound for the crossing number of the n-cube, Math. Slovaca 50 (2000) 271-287.

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

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

Send comments to Bojan.Mohar@uni-lj.si

Revised: junij 15, 2001.