Пятница, 18 октября, ауд. 203. Начало в 15:00.
Докладчик: Данила Черкашин.
Тема: Новый алгоритм в задаче Эрдеша-Хайнала.
Abstract
Проблема Эрдеша-Хайнала -- одна из наиболее известных задач экстремальной комбинаторики. Пусть $G=(V,E)$ -- $n$-однородный гиперграф (то есть все его ребра имеют мощность $n$) таков, что его вершины нельзя правильно раскрасить в 2 цвета. Под правильной раскраской подразумевается раскраска без одноцветных ребер. Тогда $m(n)$ -- минимальное количество ребер в таком графе.
Первые нетривиальные оценки получил Эрдеш в 1963 году:
$$2^{n-1} < m(n) < const \cdot n^2 2^n$$
Верхняя оценка, хотя и получается из простых вероятностых соображений, до сих пор неизменна.
Нижнюю оценку многократно улучшали, в последний раз это сделали Радхакришнан и Сринивасан в 2000 году.
$$const (n/ln(n))^{1/2}2^{n} < m(n)$$
Я расскажу о том, как повторить результат индусов более простым методом, а также как получить новые результаты в естественном обобщении задачи для $r$ цветов.
