|
ВИДЕОТЕКА |
Workshop on Extremal Graph Theory
|
|||
|
Improved algorithms for colorings of simple hypergraphs and applications D. A. Shabanov M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics |
|||
Аннотация: The famous Lovász Local Lemma was derived in the paper of P. Erdős and Lovász to prove that any $$ \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 $$ \Delta(H) \geq c \cdot nr^{n-1}, $$ where Язык доклада: английский Website: https://tech.yandex.ru/events/workshops/msk-jun-2014/talks/1912 |