2018/05/16 by Petra Mutzel, Lutz Oettershagen, Mutzel, Petra +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.1805.06780
arXiv admin note: substantial text overlap with arXiv:1803.07515 Changes in updated version: - Title was changed: The reason is that the new class of drawings is not a superset of seq-shellable drawings and is only defined for odd n. Therefore the new name is a better fit. - Minor corrections of typos and language - Clearer introduction
arxiv created 2018/07/11 · arxiv updated 2018/07/12
The Harary-Hill Conjecture states that for n≥ 3 every drawing of Kn has at least H(n) := (1)/(4)\lfloor(n)/(2)\rfloor\lfloor(n-1)/(2)\rfloor\lfloor(n-2)/(2)\rfloor\lfloor(n-3)/(2)\rfloor crossings. In general the problem remains unsolved, however there has been some success in proving the conjecture for restricted classes of drawings. The most recent and most general of these classes is seq-shellability. In this work, we improve these results and introduce the new class of semi-pair-shellable drawings. We prove the Harary-Hill Conjecture for this new class using novel results on k-edges. So far, approaches for proving the Harary-Hill Conjecture for specific classes rely on a fixed reference face. We successfully apply new techniques in order to loosen this restriction, which enables us to select different reference faces when considering subdrawings. Furthermore, we introduce the notion of k-deviations as the difference between an optimal and the actual number of k-edges. Using k-deviations, we gain interesting insights into the essence of k-edges, and we further relax the necessity of fixed reference faces.