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

Экстремальная теория графов исследует, насколько большим или плотным может быть граф, избегая при этом предписанной подструктуры, и определяет экстремальные конфигурации.

Definition

Изучение максимального или минимального значения параметра графа, такого как количество рёбер, при структурном ограничении, таком как отсутствие фиксированного подграфа.

Scope

Эта тема сосредоточена на задачах типа Турана — максимальном количестве рёбер в графе без заданного подграфа — начиная с теорем Мантеля и Турана и распространяясь на теорему Эрдёша-Стоуна, которая определяет асимптотическую экстремальную плотность для любого запрещённого подграфа. Она вводит взаимодействие плотности, структуры и метода регулярности Семереди.

Core questions

• Каково максимальное количество рёбер в графе с n вершинами, который не содержит копии заданного подграфа?
• Какие графы достигают этих экстремальных границ?
• Как хроматическое число запрещённого подграфа определяет асимптотический ответ?
• Как методы регулярности сводят плотные графы к ограниченной структуре?

Key concepts

• Запрещённые подграфы
• Граф Турана
• Теорема Мантеля
• Экстремальное число (число Турана)
• Теорема Эрдёша-Стоуна
• Лемма регулярности Семереди

Key theories

Теорема Турана

Среди всех графов с n вершинами, не содержащих полного подграфа с r+1 вершиной, сбалансированный полный r-дольный граф имеет наибольшее количество рёбер, обобщая границу Мантеля для графов без треугольников и являясь основой экстремальной теории графов.

Теорема Эрдёша-Стоуна

Для любого фиксированного запрещённого подграфа H максимальная плотность рёбер графа, не содержащего H, асимптотически определяется хроматическим числом H, объединяя экстремальные результаты типа Турана.

Clinical relevance

Результаты экстремальной плотности ограничивают структуру больших сетей и систем ограничений, а метод регулярности, разработанный в этой области, находит применение в тестировании свойств, теоретической информатике и аддитивной комбинаторике.

History

Граница Мантеля для графов без треугольников 1907 года и обобщение Турана 1941 года положили начало этой области; теория Эрдёша-Стоуна-Симоновица и лемма регулярности Семереди сделали её центральным столпом современной комбинаторики.

Key figures

• Paul Turan
• Paul Erdos
• Endre Szemeredi

Seminal works

• bollobas1998
• diestel2017

Frequently asked questions

Что такое задача типа Турана?

Она ставит вопрос о наибольшем количестве рёбер, которое может иметь граф, избегая при этом фиксированного подграфа; каноническим примером является максимальное количество рёбер в графе без треугольников.

Как экстремальная теория графов связана с теорией Рамсея?

Обе изучают неизбежную структуру, но экстремальная теория фиксирует запрещённый подграф и максимизирует рёбра, тогда как теория Рамсея гарантирует монохроматическую структуру, как только граф становится достаточно большим.