The Crossing Number of Seq-Shellable Drawings of Complete Graphs

Petra Mutzel, Lutz OettershagenarXiv 2018 · arXiv

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.

Geometric configurations illustrating the topological criteria for seq-shellability and vertex sequences.

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.

A representative drawing demonstrating the properties of seq-shellability through vertex removal (a to b).

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

Abstract

The Harary-Hill conjecture states that for every $n>0$ the complete graph on $n$ vertices $K_n$, the minimum number of crossings over all its possible drawings equals \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\text{.} \end{align*} So far, the lower bound of the conjecture could only be verified for arbitrary drawings of $K_n$ with $n\leq 12$. In recent years, progress has been made in verifying the conjecture for certain classes of drawings, for example $2$-page-book, $x$-monotone, $x$-bounded, shellable and bishellable drawings. Up to now, the class of bishellable drawings was the broadest class for which the Harary-Hill conjecture has been verified, as it contains all beforehand mentioned classes. In this work, we introduce the class of seq-shellable drawings and verify the Harary-Hill conjecture for this new class. We show that bishellability implies seq-shellability and exhibit a non-bishellable but seq-shellable drawing of $K_{11}$, therefore the class of seq-shellable drawings strictly contains the class of bishellable drawings.
BibTeX
@misc{mutzel2018crossing,
  author = {Petra Mutzel and Lutz Oettershagen},
  title = {{The Crossing Number of Seq-Shellable Drawings of Complete Graphs}},
  year = {2018},
  eprint = {1803.07515},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.07515},
}
Figure