##
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_{4})
= 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.