The polynomial noncrossing-path conjecture

A complete nn-vertex simple topological graph is a drawing of the complete graph on nn vertices in which vertices are points and edges are simple curves, with no edge passing through a nonincident vertex and with any two edges meeting at most once. A noncrossing path is a path whose edges do not cross. Polynomial noncrossing-path conjecture. There is an absolute constant ε>0\varepsilon>0 such that every complete nn-vertex simple topological graph contains a noncrossing path on nεn^{\varepsilon} vertices. The conjecture would improve the known lower bound of order lognloglogn\frac{\log n}{\log\log n} for noncrossing paths; the source states no resolution.

Sources & referencesView supporting material

Primary source

Andrew Suk, “On short edges in complete topological graphs”, arXiv:2307.08165 (2023).

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.