Ramsey properties of string graphs

Istvan Tomon (ETH Zurich)

03-May-2021, 14:00-15:00 (3 years ago)

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).

Organizers: Jan Hladky*, Diana Piguet, Jan Volec*, Liana Yepremyan
*contact for this listing

Export talk to