The crossing-degree conjecture for complete simple topological graphs

Let h=h(n)h=h(n) be the smallest integer such that every complete nn-vertex simple topological graph contains an edge crossing at most hh other edges. A simple topological graph is a graph drawn in the plane so that vertices are distinct points, edges are simple arcs joining their endpoints, no edge contains a vertex other than its endpoints, and every pair of edges intersects at most once, either at a common endpoint or at a proper crossing.

Crossing-degree conjecture. There is an absolute constant ε>0\varepsilon>0 such that

h(n)n2ε.h(n)\leq n^{2-\varepsilon}.

The source records the lower bound h(n)=Ω(n3/2)h(n)=\Omega(n^{3/2}) and upper bounds of order n2/(logn)1/2o(1)n^2/(\log n)^{1/2-o(1)}. The conjecture seeks a polynomial improvement over the quadratic upper bound and remains open.

Sources & referencesView supporting material

Primary source

Andrew Suk and Ji Zeng, “Unavoidable patterns in complete simple topological graphs”, arXiv:2204.04293 (2022).

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.