Disjoint crossing families conjecture for geometric graphs

About 16 years old · traced to

A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. For integers k,l≥1k,l\geq 1, a (k,l)(k,l)-crossing family is a pair of edge subsets E1,E2E_1,E_2 such that ∣E1∣=k|E_1|=k, ∣E2∣=l|E_2|=l, the edges in each subset are pairwise crossing, and every edge in E1E_1 is disjoint from every edge in E2E_2. Disjoint crossing families conjecture. Given fixed constants k,l≥1k,l\geq 1, there exists a constant ck,lc_{k,l} such that any geometric graph on nn vertices with no (k,l)(k,l)-crossing family has at most ck,lnc_{k,l}n edges. The conjecture is an extremal question about forbidden crossing and disjointness patterns in geometric graphs. The case (k,l)=(2,1)(k,l)=(2,1) is proved with an O(n)O(n) bound, while the general case remains open; the analogous assertion for topological graphs is false.

References

Primary source

Radoslav Fulek and Andrew Suk, “On disjoint crossing families in geometric graphs”, arXiv:1004.2850 (2011).

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.