The following Ramsey-type question is one of the central problems in combinatorial geometry. Given a collection of certain geometric objects in the plane (e.g. segments, rectangles, convex sets, arcwise connected sets) of size n , what is the size of the largest subcollection in which either any two elements have a nonempty intersection, or any two elements are disjoint? We prove that there exists an absolute constant c>0 such that if C is a collection of n curves in the plane, then C contains at least nᶜ elements that are pairwise intersecting, or nᶜ elements that are pairwise disjoint. This resolves a problem raised by Alon, Pach, Pinchasi, Radoičić and Sharir, and Fox and Pach. Furthermore, as any geometric object can be arbitrarily closely approximated by a curve, this shows that the answer to the aforementioned question is at least nᶜ for any collection of n geometric objects.
No takes yet. Share an insight, caveat, or question.
István Tomon (2023) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: