|
|
Семинар отдела дискретной математики МИАН
2 сентября 2008 г. 16:00, г. Москва, МИАН, комн. 511 (ул. Губкина, 8)
|
|
|
|
|
|
Плотность числа треугольников в графах с известной плотностью рёбер
А. А. Разборов |
Количество просмотров: |
Эта страница: | 383 |
|
Аннотация:
Какова минимально возможная плотность $g(\rho)$ числа треугольников в графе с данной плотностью рёбер $\rho$? Классическая теорема Mantel (1907) утверждает, что $g(\rho)>0$ при $\rho>1/2$. Частичные уточнения этой теоремы были получены в работах Goodman (1959), Bollobas (1975), Lovasz, Simonovits (1983) и Fisher (1989).
Нами получено полное решение данной проблемы. Помимо этого конкретного результата, значительная часть доклада будет посвящена развитой докладчиком общей методологии (алгебры флагов), с помощью которой, в частности, оно и было получен. Эта методология позволяет унифицировать различные методы, используемые в экстремальной комбинаторике и по существу свести их к прозрачным (с математической точки зрения) манипуляциям в коммутативных алгебрах, во многих случаях использующим также элементы теории меры.
|
|