Back to Search Start Over

String graphs have the Erdős–Hajnal property.

Authors :
Tomon, István
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