• 5 сентября, вторник
  • Москва, ул. Льва Толстого, 16, конференц-зал "Мулен Руж"

Workshop on extremal combinatorics

Регистрация на событие закрыта

Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.

Другие события организатора

Школа Прикладной Математики и Информатики МФТИ
44 дня назад
5 сентября c 16:30 до 21:00
Москва
ул. Льва Толстого, 16, конференц-зал "Мулен Руж"

Очередной воркшоп будет проходить 5 сентября в Яндексе

Экстремальная комбинаторика − один из самых красивых разделов дискретной математики. С одной стороны, в нем очень много глубокой математики. С другой стороны, экстремальная комбинаторика имеет множество приложений в С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
Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erdos-Ko-Rado theorem. On the other hand, P. Erdos and L. Lovasz posed problems on coloring intersecting families as a restriction of classical hypergraph coloring problems to a special class of hypergraphs. We deal with the mentioned coloring problems stated for 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 
One of the simplest objects are finite sets. For a positive integer n let [n] denote the set of integers 1,2,…,n. Let 2^[n] be the power set of [n] (it consists of 2^n subsets. Any subset F of 2^[n] is called a family. Extremal set theory is dealing with (best possible) upper bounds on |F|, the number of subsets in F, subject to some conditions imposed on F. For example, the classical theorem of Sperner (1928) states that if no member of F contains another then |F| is at most the largest binomial coefficient. We are going to present several results and problems of similar flavour.  
  • 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.

Регистрация

Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше