City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Бесповторность
Word combinatorics and its applications

What: Lecture
When: Thursday, 26 March 2015, 18:30–20:00
Where: ПОМИ РАН
Slides: wordscombinatorics_lecture_260315.pdf

Description

Бесповторность. Квадраты и кубы. Слова Туэ-Морса, теорема о сильной бескубности. Избегаемые экспоненты. Слова Аршона, теорема о 7/4. Граничная теорема (гипотеза Дежан). Цилиндрические слова. Бесповторные раскраски графов. Циклические слова и граф К33 Шаблоны, их избегание. Неизбежные шаблоны. Слова Зимина. Критерий неизбежности (Бина- Эренфойхта-Макналти-Зимина). Алгоритмические проблемы о словах Зимина. Генератор случайных бесквадратных слов.

Video