Linear disjoint edges in complete topological graphs
Optimal disjoint-edges bound in complete simple topological graphs · arXiv:2312.01028
Status open high confidence
The best known lower bound for pairwise disjoint edges in a complete $n$-vertex simple topological graph is $\Omega(n^{1/2})$, established by Aichholzer, García, Tejel, Vogtenhuber, and Weinberger (SoCG 2022, arXiv:2203.06143), improving the earlier $\Omega(n^{1/3})$ bound of Suk (2012). The source paper (Fox–Pach–Suk, 2023) provides a nearly-polynomial improvement under a density assumption via a pseudo-segment regularity lemma, but the full $\Omega(n)$ conjecture remains open. No post-2023 paper resolving the problem was found in a broad web search.
Reviewer notes. The Omega(n^{1/2}) bound (Aichholzer et al., SoCG 2022, arXiv:2203.06143) is the current state of the art; the source paper improves this to a nearly-polynomial bound only under an edge-density assumption (Corollary 1.3). The paper 2512.04795 (December 2025) addresses plane paths in dense topological graphs but does not resolve the disjoint-edges question. No follow-up resolving the full Omega(n) conjecture was found.
Context
Aichholzer et al. [2] showed that every complete $n$-vertex simple topological graph always contains $\Omega(n^{1/2})$ pairwise disjoint edges. The paper notes that improving this lower bound to $\Omega(n)$ is an open problem, and Corollary 1.3 provides a new nearly-polynomial lower bound under a density assumption.
Notes. Stated in passing as an open problem without a labelled theorem environment; PDF source.
Source paper
A structure theorem for pseudo-segments and its applications
Jacob Fox, Janos Pach, Andrew Suk · 2023-12-02
https://arxiv.org/abs/2312.01028
PDF source