RUS  ENG
Полная версия
ВИДЕОТЕКА

Дни комбинаторики и геометрии II
13 апреля 2020 г. 17:10, Онлайн-конференция


String graphs have the Erdös-Hajnal property

I. Tomon


https://youtu.be/cZyJ4VwuCCA

Аннотация: A string graph is the intersection graph of curves in the plane. Building on previous works of Fox and Pach [1, 2], we prove that there exists an absolute constant $c>0$ such that if $G$ is a string graph on $n$ vertices, then $G$ contains either a clique or an independent set of size at least $n^c$.

[1] J. Fox and J. Pach, Erdös-Hajnal-type results on intersection patterns of geo-metric objects, in Horizons of combinatorics, G. O. H. Katona et al., eds., Bolyai Soc. Stud. Math. 17, Springer, Berlin, Heidelberg, (2008), 79—103. \newine
[2] J. Fox and J. Pach, String graphs and incomparability graphs, Advances in Mathematics 230 (2012), 1381—1401.


© МИАН, 2024