arXiv Open Access 2013

Shellable drawings and the cylindrical crossing number of $K_n$

Bernardo M. Ábrego Oswin Aichholzer Silvia Fernández-Merchant Pedro Ramos Gelasio Salazar
Lihat Sumber

Abstrak

The Harary-Hill Conjecture States that the number of crossings in any drawing of the complete graph $ K_n $ in the plane is at least $Z(n):=\frac{1}{4}\left\lfloor \frac{n}{2}\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor \frac{n-2}{2}\right\rfloor\left\lfloor \frac{n-3}{2}\right\rfloor$. In this paper, we settle the Harary-Hill conjecture for {\em shellable drawings}. We say that a drawing $D$ of $ K_n $ is {\em $ s $-shellable} if there exist a subset $ S = \{v_1,v_2,\ldots,v_ s\}$ of the vertices and a region $R$ of $D$ with the following property: For all $1 \leq i < j \leq s$, if $D_{ij}$ is the drawing obtained from $D$ by removing $v_1,v_2,\ldots v_{i-1},v_{j+1},\ldots,v_{s}$, then $v_i$ and $v_j$ are on the boundary of the region of $D_{ij}$ that contains $R$. For $ s\geq n/2 $, we prove that the number of crossings of any $ s $-shellable drawing of $ K_n $ is at least the long-conjectured value Z(n). Furthermore, we prove that all cylindrical, $ x $-bounded, monotone, and 2-page drawings of $ K_n $ are $ s $-shellable for some $ s\geq n/2 $ and thus they all have at least $ Z(n) $ crossings. The techniques developed provide a unified proof of the Harary-Hill conjecture for these classes of drawings.

Topik & Kata Kunci

Penulis (5)

B

Bernardo M. Ábrego

O

Oswin Aichholzer

S

Silvia Fernández-Merchant

P

Pedro Ramos

G

Gelasio Salazar

Format Sitasi

Ábrego, B.M., Aichholzer, O., Fernández-Merchant, S., Ramos, P., Salazar, G. (2013). Shellable drawings and the cylindrical crossing number of $K_n$. https://arxiv.org/abs/1309.3665

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2013
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓