Home

Пятница 18 октября, 15-00, ауд. 203

Пятница, 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 $ цветов.