Home

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

  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-1 has been created.
  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-2 has been created.
  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-3 has been created.
  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-4 has been created.
  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-5 has been created.
  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-6 has been created.
  • The directory /tmp/drutex-03ac98aa5627d58f321f07daf9ae6559-7 has been created.

Пятница, 18 октября, ауд. 203. Начало в 15:00.

Докладчик: Данила Черкашин.

Тема: Новый алгоритм в задаче Эрдеша-Хайнала.

Abstract

Проблема Эрдеша-Хайнала -- одна из наиболее известных задач экстремальной комбинаторики. Пусть TeX Embedding failed! -- TeX Embedding failed!-однородный гиперграф (то есть все его ребра имеют мощность TeX Embedding failed!) таков, что его вершины нельзя правильно раскрасить в 2 цвета. Под правильной раскраской подразумевается раскраска без одноцветных ребер. Тогда TeX Embedding failed! -- минимальное количество ребер в таком графе. Первые нетривиальные оценки получил Эрдеш в 1963 году:
TeX Embedding failed!
Верхняя оценка, хотя и получается из простых вероятностых соображений, до сих пор неизменна. Нижнюю оценку многократно улучшали, в последний раз это сделали Радхакришнан и Сринивасан в 2000 году.
TeX Embedding failed!
Я расскажу о том, как повторить результат индусов более простым методом, а также как получить новые результаты в естественном обобщении задачи для TeX Embedding failed! цветов.