The Nase conjecture on triple cumulative edge bounds in simple graph drawings

From papers

Let DD be a simple drawing of a graph, and let Ek(D)E_{{\le}{\le}{\le}k}(D) denote the number of its  ⁣ ⁣k\le\!\le\!\le k-edges, defined by

Ek(D)=j=0kEj(D)=i=0k(k+2i2)Ei(D).E_{{\le}{\le}{\le}k}(D)=\sum_{j=0}^{k}E_{{\le}{\le}j}(D)=\sum_{i=0}^{k}{k+2-i\choose 2}E_i(D).

Here Ei(D)E_i(D) denotes the number of ii-edges, and the cumulative notation is obtained by summing the corresponding lower-order edge counts. The Nase conjecture. If n3n\ge 3 and DD is a simple drawing of KnK_n, then for every kk satisfying 0k<n/210\le k<n/2-1,

Ek(D)3(k+44).E_{{\le}{\le}{\le}k}(D)\ge 3{k+4\choose 4}.

The conjecture is stronger than Hill's conjecture. It is implied by the paper's theorem for simple xx-monotone drawings, and all examples considered by the authors satisfy it; its validity for arbitrary simple drawings remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Martin Balko, Radoslav Fulek and Jan Kynčl, “Crossing numbers and combinatorial characterization of monotone drawings of K_n”, arXiv:1312.3679 (2014).

Solutions 0

No solutions have been posted yet.