Экстремальная теория графов

Экстремальная теория графов отвечает на вопрос: сколько рёбер может быть у графа без заданного подграфа? Ответы неожиданно точны и часто достигаются единственной конструкцией.

• **Сети без кластеров:** социальные сети с ограниченным числом треугольников исследуются через числа Турана
• **Коды и expanders:** Ramsey-теория связана с построением кодов с заданными расстояниями
• **Вычислительная геометрия:** числа пересечений конфигураций точек определяются через экстремальные задачи на графах

Предварительные знания

• Теория графов (основы)
• Алгебраическая теория графов
• Комбинаторика
• Вероятностный метод

• Algebraic Graph Theory

Теорема Турана и числа Турана

Пол Туран сформулировал задачу в будапештском лагере для интернированных в 1941 году: граф из n вершин без треугольника содержит не более n^2/4 рёбер. Этот результат стал основой современной экстремальной комбинаторики.

Числа Рамсея

Задача Рамсея появилась в работе Фрэнка Рамсея 1930 года. Для R(3,3)=6: любая раскраска K_6 в 2 цвета содержит одноцветный треугольник. Нижний предел R(5,5) неизвестен с точностью до десятков: от 43 до 48.

Ключевые идеи

• **Теорема Турана:** ex(n,K_{r+1}) = (1-1/r)*n^2/2; экстремальный граф T(n,r) - равнодольный r-дольный
• **Теорема Мантела:** ex(n,K_3) = floor(n^2/4); без треугольников максимум рёбер - в K_{n/2,n/2}
• **Теорема Эрдёша-Стоуна:** ex(n,H) = (1-1/(chi(H)-1))*n^2/2 + o(n^2); только хроматическое число важно асимптотически
• **Числа Рамсея R(s,t):** нижняя граница 2^{t/2} через вероятностный метод; R(5,5) неизвестно точно

Вопросы для размышления

• Почему точность теоремы Эрдёша-Стоуна ломается для двудольных графов H (chi(H)=2)?
• Как вероятностный метод Эрдёша доказывает нижнюю границу R(t,t) >= 2^{t/2}?
• Что означает, что граф Турана T(n,r) - единственный экстремальный граф? Как это доказать?

Связанные уроки

• prob-02-combinatorics