Introduction
The crossing number of a graph, denoted $cr(G)$, is the minimum number of edge crossings in any drawing of $G$ in the plane. For complete graphs $K_n$, the Harary-Hill Conjecture posits that the minimum crossing number is given by the formula:
$$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$$
While this conjecture has stood since the 1960s, proving it for all possible drawings remains an open challenge. Recent progress has focused on specific classes of drawings, such as shellable or monotone drawings. This paper, presented at the 30th Canadian Conference on Computational Geometry (CCCG 2018), introduces a new, broader class called semi-pair-shellable drawings.
Breaking Global Constraints
A significant hurdle in previous proofs was the reliance on a "globally fixed reference face." In these frameworks, the entire drawing must maintain a specific structural relationship with a single outer boundary. The authors break this limitation by allowing for "local" changes to the reference face during the proof process.
Methodology and Key Innovations
The authors utilize the theory of $k$-edges. An edge is defined as a $k$-edge if it partitions the remaining vertices into sets of size $k$ and $n-k-2$ relative to a specific reference face. To achieve their results, they introduced several novel mathematical tools:
- Triple Cumulated $k$-edges: A refined summation technique for tighter lower bounds on crossings.
- Semi-Pair-Shellability: A property where vertices are removed in pairs (a "pair-sequence"), allowing the reference face to shift dynamically rather than staying fixed.
- $k$-deviations: A metric quantifying the gap between a drawing's actual $k$-edge count and the theoretical optimum predicted by Harary-Hill.
The core innovation lies in the ability to "hop" between reference faces. As shown in Figure 4, the analysis can transition from one face $F$ to an adjacent face $F'$, relaxing the rigid constraints of earlier methods.
Results and Implications
The primary result, Theorem 15, states that any semi-pair-shellable drawing of $K_n$ satisfies the Harary-Hill Conjecture: $cr(D) \geq H(n)$. This significantly expands the set of drawings for which the conjecture is known to hold. Notably, the authors demonstrate that semi-pair-shellable drawings are a strictly larger class than previously studied "seq-shellable" drawings, providing a specific example of a $K_{11}$ drawing that is semi-pair-shellable but not seq-shellable.
Conclusion and Future Directions
While this work represents a major step forward, the Harary-Hill Conjecture is not yet fully resolved. The current definition of semi-pair-shellability is primarily optimized for graphs with an odd number of vertices; extending these results to even $n$ remains an open challenge. Additionally, the authors propose a new "Deviation Conjecture" regarding the behavior of $k$-deviations, which could further generalize the classes of drawings that meet the $H(n)$ bound.
Summary updated