Введение

Теория экстремальных графов — это раздел комбинаторики, являющейся областью математики, который находится на пересечении экстремальной комбинаторики и теории графов. По сути, теория экстремальных графов изучает, как глобальные свойства графа влияют на его локальную структуру. Результаты в теории экстремальных графов устанавливают количественные связи между различными свойствами графов, как глобальными (например, число вершин и рёбер), так и локальными (например, наличие определённых подграфов), а задачи в теории экстремальных графов часто формулируются как задачи оптимизации: каким максимальным или минимальным может быть параметр графа при заданных ограничениях, которым должен удовлетворять граф? Граф, являющийся оптимальным решением такой задачи оптимизации, называется экстремальным графом, и экстремальные графы представляют собой важные объекты изучения в теории экстремальных графов. Теория экстремальных графов тесно связана с такими областями, как теория Рамсея, спектральная теория графов, теория вычислительной сложности и аддитивная комбинаторика, и часто использует вероятностный метод.

История

Теорема Мантеля (1907) и теорема Турана (1941) стали одними из первых важных результатов в изучении экстремальной теории графов. В частности, теорема Турана впоследствии послужила мотивацией для получения таких результатов, как теорема Эрдеша — Стона (1946). Этот результат примечателен тем, что связывает хроматическое число с максимальным количеством ребер в графе, не содержащем заданную подструктуру. Альтернативное доказательство теоремы Эрдеша — Стона было предложено в 1975 году и использовало лемму о регулярности Семереди, являющуюся ключевым инструментом в решении задач экстремальной теории графов.

Цвет графика

Соответствующее (вершинное) раскрашивание графа – это раскраска вершин графа таким образом, чтобы любые две смежные вершины имели разные цвета. Минимальное количество цветов, необходимое для корректной раскраски графа, называется хроматическим числом графа и обозначается χ(G). Определение хроматического числа конкретных графов является фундаментальным вопросом в экстремальной теории графов, поскольку многие задачи в этой и смежных областях могут быть сформулированы в терминах раскраски графов. Двумя простыми нижними границами для хроматического числа графа G являются число клики (все вершины клики должны иметь различные цвета) и G/α(G), где α(G) – число независимости, поскольку множество вершин, окрашенных в один цвет, должно образовывать независимое множество. Жадный алгоритм раскраски даёт верхнюю границу Δ(G) + 1, где Δ(G) – максимальная степень графа. Если G не является нечётным циклом или кликой, то теорема Брукса утверждает, что верхнюю границу можно уменьшить до Δ(G). Если G – планарный граф, то теорема о четырёх цветах утверждает, что его хроматическое число не превосходит четырёх. В общем случае, определение того, имеет ли данный граф раскраску заданным числом цветов, является NP-трудной задачей. Помимо раскраски вершин, изучаются и другие типы раскрасок, такие как раскраски рёбер. Хроматический индекс графа – это минимальное число цветов в корректной раскраске рёбер графа, и теорема Визинга утверждает, что хроматический индекс графа равен либо Δ(G), либо Δ(G) + 1.

Запрещенные подграфы

Запрещенная подграфа — одна из центральных задач в экстремальной теории графов. Для заданного графа , задача о запрещенной подграфе ставит вопрос об определении максимального числа ребер в графе на вершинах, который не содержит подграф, изоморфный .

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

Плотность гомоморфизма

Плотность гомоморфизма графа в графе описывает вероятность того, что случайное отображение из множества вершин в множество вершин также является гомоморфизмом графа. Она тесно связана с плотностью подграфов, которая описывает, как часто граф встречается в качестве подграфа другого графа. Задача о запрещенных подграфах может быть переформулирована как задача максимизации плотности ребер графа с нулевой плотностью, что естественным образом приводит к обобщениям в виде неравенств гомоморфизма графов – неравенств, связывающих плотности гомоморфизмов для различных графов. Расширяя понятие плотности гомоморфизма на графоны, являющиеся пределом плотных графов, плотность гомоморфизма можно представить в виде интегралов, и такие неравенства, как неравенство Коши — Буняковского — Шварца и неравенство Гёльдера, могут быть использованы для вывода неравенств гомоморфизма. Важной нерешенной проблемой, связанной с плотностью гомоморфизмов, является гипотеза Сидоренко, утверждающая существование точной нижней границы для плотности гомоморфизма двудольного графа в графе, выраженной через плотность ребер этого графа.

Графическая регулярность

Лемма регулярности Семереди утверждает, что все графы "регулярны" в следующем смысле: множество вершин любого заданного графа можно разбить на ограниченное число частей таким образом, что двудольный граф между большинством пар частей ведёт себя как случайный двудольный граф. Это разбиение даёт структурную аппроксимацию исходного графа, которая раскрывает информацию о свойствах исходного графа. Лемма регулярности является центральным результатом в экстремальной теории графов, а также имеет многочисленные применения в смежных областях аддитивной комбинаторики и теории вычислительной сложности. Помимо регулярности (Семереди), также изучались тесно связанные понятия регулярности графов, такие как сильная регулярность и слабая регулярность Фриза — Каннана, а также обобщения регулярности на гиперграфы. Применения регулярности графов часто используют различные варианты лемм подсчёта и лемм удаления. В простейших формах лемма подсчёта графов использует регулярность между парами частей в регулярном разбиении для приближённого вычисления количества подграфов, а лемма удаления графов утверждает, что если задан граф с небольшим количеством копий заданного подграфа, то можно удалить небольшое число рёбер, чтобы устранить все копии этого подграфа.