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

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





Для просмотра файлов Вам могут потребоваться






Workshop on Extremal Graph Theory
6 июня 2014 г. 11:30, г. Москва, Московский офис Яндекса, ул. Льва Толстого, д. 16
 


Improved algorithms for colorings of simple hypergraphs and applications

D. A. Shabanov

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Количество просмотров:
Эта страница:57
Видеофайлы:21



Аннотация: The famous Lovász Local Lemma was derived in the paper of P. Erdős and Lovász to prove that any $n$-uniform non-$r$-colorable hypergraph $H$ has maximum edge degree at least
$$ \Delta(H) \geq \frac14 r^{n-1}. $$
A long series of papers is devoted to the improvement of this classical result for different classesof uniform hypergraphs.
In our work we deal with colorings of simple hypergraphs, i.e. hypergraphs in which everytwo distinct edges do not share more than one vertex. By using a multipass random recoloringwe show that any simple $n$-uniform non-$r$-colorable hypergraph $H$ has maximum edge degree at least
$$ \Delta(H) \geq c \cdot nr^{n-1}, $$
where $c > 0$ is an absolute constant. We also give some applications of our probabilistic technique, we establish a new lower bound for the Van der Waerden number and extend the main result to the $b$-simple case.

Язык доклада: английский

Website: http://tech.yandex.ru/events/workshops/msk-jun-2014/talks/1912

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017