2015/10/02 by Bernardo M. Ábrego, Oswin Aichholzer, Ábrego, Bernardo M. +15
Computer Science · Mathematics · #05C10 #68R10 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.CO #msc:05C10 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1510.00549
11 pages, 5 figures. updated, extended version
arxiv created 2018/07/12 · arxiv updated 2018/07/16
The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph Kn is H(n) = \frac 1 4 \lfloor(\mathstrut n)/(\mathstrut 2)\rfloor \lfloor(\mathstrut n-1)/(\mathstrut 2)\rfloor \lfloor(\mathstrut n-2)/(\mathstrut 2)\rfloor \lfloor(\mathstrut n-3)/(\mathstrut 2) \rfloor. Ábrego et al. introduced the notion of shellability of a drawing D of Kn. They proved that if D is s-shellable for some s≥\lfloor(n)/(2)\rfloor, then D has at least H(n) crossings. This is the first combinatorial condition on a drawing that guarantees at least H(n) crossings. In this work, we generalize the concept of s-shellability to bishellability, where the former implies the latter in the sense that every s-shellable drawing is, for any b ≤ s-2, also b-bishellable. Our main result is that (\lfloor (n)/(2) \rfloor - 2)-bishellability of a drawing D of Kn also guarantees, with a simpler proof than for s-shellability, that D has at least H(n) crossings. We exhibit a drawing of K11 that has H(11) crossings, is 3-bishellable, and is not s-shellable for any s≥5. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved. Moreover, we provide an infinite family of drawings of Kn that are (\lfloor (n)/(2) \rfloor - 2)-bishellable, but not s-shellable for any s≥\lfloor(n)/(2)\rfloor.