Guy, Richard K.


The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

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.

\begin{conjecture} $\displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32}$ \end{conjecture}

Keywords: crossing number; hypercube

Syndicate content