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