Premium
An improved upper bound on the crossing number of the hypercube
Author(s) -
Faria Luerbio,
Herrera de Figueiredo Celina Miraglia,
Sýkora Ondrej,
Vrt'o Imrich
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20330
Subject(s) - hypercube , combinatorics , mathematics , upper and lower bounds , crossing number (knot theory) , graph , plane (geometry) , discrete mathematics , geometry , mathematical analysis , intersection (aeronautics) , engineering , aerospace engineering
We draw the n ‐dimensional hypercube in the plane with ${5\over 32}4^{n}-\lfloor{{{{n}^{2}+1}\over 2}}\rfloor {2}^{n-2}$ crossings, which improves the previous best estimation and coincides with the long conjectured upper bound of Erdös and Guy. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 145–161, 2008