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

About 13 years old · traced to

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

E≤≤≤k(D)=∑j=0kE≤≤j(D)=∑i=0k(k+2−i2)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 n≥3n\ge 3 and DD is a simple drawing of KnK_n, then for every kk satisfying 0≤k<n/2−10\le k<n/2-1,

E≤≤≤k(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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.