Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






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


String graphs have the Erdös-Hajnal property

I. Tomon
Дополнительные материалы:
Adobe PDF 284.8 Kb

Количество просмотров:
Эта страница:87
Материалы:20
Youtube:



Аннотация: 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.

Дополнительные материалы: istvan_tomon.pdf (284.8 Kb)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024