Back to Search
Start Over
String graphs have the Erdős–Hajnal property.
- Source :
-
Journal of the European Mathematical Society (EMS Publishing) . 2024, Vol. 26 Issue 1, p275-287. 13p. - Publication Year :
- 2024
-
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 nc 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]
Details
- Language :
- English
- ISSN :
- 14359855
- Volume :
- 26
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of the European Mathematical Society (EMS Publishing)
- Publication Type :
- Academic Journal
- Accession number :
- 175485223
- Full Text :
- https://doi.org/10.4171/JEMS/1362