Abstract
The Harary-Hill conjecture provides a lower bound for the number of edge crossings in drawings of the complete graph $K_n$. While verified for specific classes such as bishellable drawings, a general proof remains one of the most significant open problems in topological graph theory. This paper introduces "seq-shellable drawings," a novel and more flexible class that generalizes bishellability. We prove that the Harary-Hill conjecture holds for all seq-shellable drawings, thereby expanding the set of known cases. Furthermore, we demonstrate that this new class is strictly larger than the bishellable class by providing a non-bishellable, seq-shellable drawing of $K_{11}$.
Introduction
Determining the crossing number of the complete graph $K_n$ is a fundamental challenge in discrete mathematics. The Harary-Hill Conjecture suggests that the minimum number of crossings is $H(n) = \frac{1}{4} \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$. Despite its simplicity, the conjecture has only been confirmed for general drawings with $n \le 12$. Consequently, research has focused on proving the conjecture for specific restricted classes of drawings. Until recently, "bishellable" drawings represented the most inclusive such class. This work introduces "seq-shellability," a generalization that relaxes the symmetry requirements of bishellability, and confirms the conjecture for this broader category.
Methods
The authors define seq-shellability through the concept of "simple sequences" of vertices. A sequence is simple if each vertex can be placed on a specific reference face in successive sub-drawings created by vertex removal. Unlike bishellability, which requires a symmetric relationship between two sequences, seq-shellability allows for asymmetric vertex sequences, providing greater flexibility in graph construction.
The mathematical proof employs a recursive counting technique centered on "cumulated $k$-edges." A $k$-edge is an edge that partitions the remaining $n-2$ vertices into sets of size $k$ and $n-k-2$. By analyzing how these edges behave when vertices are removed, the authors use induction to show that seq-shellable drawings always contain enough crossings to meet the $H(n)$ bound. The property of "invariant edges"—those that preserve their $k$-value across sub-drawings—is critical to this inductive step.
Results
The study successfully proves that for any $(\lfloor n/2 \rfloor - 2)$-seq-shellable drawing of $K_n$, the number of crossings is at least $H(n)$. A key contribution is the formal demonstration that the class of bishellable drawings is a proper subset of seq-shellable drawings.
To establish this strict containment, the authors analyzed specific drawings of $K_{11}$ and $K_{14}$. They identified a drawing of $K_{11}$ that is seq-shellable but cannot be classified as bishellable. This "benchmark drawing" serves as a proof-of-concept, showing that the new theory covers a strictly larger set of graph drawings than previous methods, narrowing the gap toward a universal proof of the Harary-Hill conjecture.
Discussion and Future Work
By broadening the class of drawings for which the Harary-Hill conjecture is verified, this work significantly expands our understanding of crossing numbers. However, several challenges remain. While the lower bound is established, general methods for constructing optimal seq-shellable drawings that are not bishellable have yet to be developed. Additionally, the authors raise questions about the existence of such drawings for other small values of $n$ (between 10 and 14). The ultimate objective continues to be proving the conjecture for all "good" drawings of $K_n$, and seq-shellability provides a powerful new tool in this ongoing pursuit.
Summary updated