The Erd\H{o}s and Guy's conjectured equality on the crossing number of hypercubes

2012 
Let $Q_n$ be the $n$-dimensional hypercube, and let ${\rm cr}(Q_n)$ be the \textit{crossing number} of $Q_n$. A long-standing conjecture proposed by Erd\H{o}s and Guy in 1973 is the following equality: ${\rm cr}(Q_n)=(5/32)4^n-\lfloor\frac{n^2+1}{2}\rfloor 2^{n-2}$. In this paper, we construct a drawing of $Q_n$ with less crossings, which implies ${\rm cr}(Q_n)\lneqq (5/32)4^n-\lfloor\frac{n^2+1}{2}\rfloor 2^{n-2}$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    10
    References
    3
    Citations
    NaN
    KQI
    []