Crossing-pairs conjecture for topological graphs

About 13 years old · traced to

A topological graph is a graph drawn in the plane with vertices represented by points and edges by curves connecting their endpoints; two edges cross when their curves intersect away from common endpoints. The crossing-pairs conjecture. In every topological graph with nn vertices and m≥4nm\geq 4n edges, there are two disjoint sets of edges, each of cardinality

Ω(m2n2log⁡mn),\Omega\left(\frac{m^2}{n^2\log\frac{m}{n}}\right),

such that every edge in one set crosses every edge in the other. The claimed bound would be tight and is presented as a consequence of the sharper extremal conjecture.

References

Primary source

Jacob Fox and Janos Pach, “Applications of a new separator theorem for string graphs”, arXiv:1302.7228 (2013).

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.