Ramsey properties of string graphs

Abstract: In this talk, I will give an outline of the proof of the following conjecture of Alon, Pach, Pinchasi, Radoicic and Sharir. There exists an absolute constant $c>0$ such that any collection of $n$ curves (or in general arcwise-connected sets) in the plane contains a subset of size $n^c$ in which any two elements intersect, or any two are disjoint. This generalizes many earlier results about the Ramsey properties of intersection graphs of geometric objects. The heart of our proof is a purely graph theoretic lemma, which turned out to be quite useful in other Erdos-Hajnal type results as well, see e.g. the recent proof of the Erdos-Hajnal conjecture for the cycle of length 5 by Chudnovsky, Scott, Seymour and Spirkl. For this talk, no knowledge of geometry is required.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).