Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes. Issue 3 (28th December 2021)

• Record Type: Journal Article
• Authors: Yang, Yuansheng; Wang, Guoqing; Wang, Haoli; Zhou, Yan
• Is Part Of: Journal of graph theory. Volume 100:Issue 3(2022)
• Page Start: 389
• Page End: 434
• Publication Date: 2021-12-28
• Subjects: crossing number -- drawing -- hypercube; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22787
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Let Q n be the n ‐dimensional hypercube, and let cr ( Q n ) be the crossing number of Q n . Erdős and Guy in 1973 conjectured the following equality: cr ( Q n ) = 5 32 4 n − n 2 + 1 2 2 n − 2 . In this paper, we construct a drawing of Q n with less crossings when n > 6, which implies that for n > 6 we have a strict inequality.