## 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 Qd is the graph whose vertices are all binary sequences of length d, and two of the sequences are adjacent in Qd if they differ in precisely one coordinate.

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

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

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.