1. String graphs have the Erdős–Hajnal property.
- Author
-
Tomon, István
- Subjects
GEOMETRIC analysis ,APPROXIMATION theory ,COMBINATORIAL geometry ,CONVEX sets ,MATHEMATICAL formulas - Abstract
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
c elements that are pairwise intersecting, or n c 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 nc for any collection of n geometric objects. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF