Экстремальная комбинаторика − один из самых красивых разделов дискретной математики. С одной стороны, в нем очень много глубокой математики. С другой стороны, экстремальная комбинаторика имеет множество приложений в Сomputer Science.
В воркшопе примут участие два крупнейших специалиста в области экстремальной комбинаторики − Петер Франкл и Вениамин Судаков. Также перед слушателями выступят сотрудники лаборатории продвинутой комбинаторики и сетевых приложений МФТИ, которая тесно взаимодействует с группой исследований и преподавания в МФТИ Яндекса.
Лекции пройдут на английском языке без перевода. Стойка регистрации работает на протяжении всего воркшопа.
Участие в воркшопе бесплатно, но количество мест ограничено. Требуется регистрация на сайте https://events.yandex.ru/events/sci....
- 16:30 Регистрация
- 17:00 Дмитрий Шабанов (МФТИ, МГУ) — Panchromatic 3-coloring of a random hypergraph
The talk deals with colorings of random hypergraphs. A vertex 3-coloring is called panchromatic for a hypergraph H if every edge of H meets every color of 3 colors under this coloring. By using the second moment method we obtain very tight bounds for the probability threshold for the property that a random hypergraph in the binomial model admits a panchromatic 3-coloring.
- 17:30 Данила Черкашин (МФТИ, СПбГУ) — Coloring cross-intersecting families
- 18:00 Максим Жуковский (МФТИ, Яндекс) — On the Le Bars conjecture
In 2001, Le Bars proved that there is an existential second order property that has no limit probability for the uniformly chosen random graph G(n,1/2). He conjectured that two first order quantifiers are enough to construct such a sentence. We prove that the conjecture is true for G(n,p) where p equals either (3-\sqrt{5})/2 or (\sqrt{5}-1)/2.
- 18:30 Cергей Киселев (МФТИ) — On the chromatic numbers of random subgraphs of Kneser graphs
A Kneser graph KG_{n,k} is a graph whose vertices are all k-element subsets of [n] and two vertices are connected if and only if the corresponding sets do not intersect. Kneser conjecture states that the chromatic number of such graph is n — 2k + 2. The conjecture was proved by Lov\’asz with the help of a topological approach.
A random subgraph KG_{n,k}(p) is a spanning subgraph of KG_{n,k} containing each edge of KG_{n,k} with probability p. The chromatic numbers of random subgraphs of Kneser graphs and their generalizations were firstly studied by Bogoliubskiy, Gusev, Pyaderkin, and Raigorodskii. A related research was done by Bollob’\as, Narayanan, Raigorodskii and others. Kupavskii obtained the best known lower bounds for the chromatic numbers of KG_{n,k}(p). He used a Lov\’asz type topological approach.
In this talk, I will give new upper and lower bounds for the chromatic numbers of KG_{n,k}(p) using a purely combinatorial approach.
- 19:00 Перерыв
- 19:20 Péter Frankl (Hungarian Academy of Sciences, Budapest) — Extremal set theory
- 20:20 Benjamin Sudakov (ETH, Zurich) — Tower-type bounds for unavoidable patterns in words
A word w is said to contain the pattern P if there is a way to substitute a nonempty word for each letter in P so that the resulting word is a subword of w. Bean, Ehrenfeucht and McNulty and, independently, Zimin characterised the patterns P which are unavoidable, in the sense that any sufficiently long word over a fixed alphabet contains P. Zimin’s characterisation says that a pattern is unavoidable if and only if it is contained in a Zimin word, where the Zimin words are defined by Z_1 = x_1 and Z_n=Z_{n-1} x_n Z_{n-1}. We study the quantitative aspects of this theorem, obtaining essentially tight tower-type bounds for the function f(n,q), the least integer such that any word of length f(n, q) over an alphabet of size q contains Z_n.