





















The Harary-Hill Conjecture states that for $n\geq 3$ every drawing of $K_n$ has at least \begin{align*} H(n) := \frac{1}{4}\Big\lfloor\frac{n}{2}\Big\rfloor\Big\lfloor\frac{n-1}{2}\Big\rfloor\Big\lfloor\frac{n-2}{2}\Big\rfloor\Big\lfloor\frac{n-3}{2}\Big\rfloor \end{align*} 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。