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

Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа^[1].

Например, простым вопросом экстремальной теории графов является вопрос «Какие ацикличные графы с n вершинами имеют максимальное число рёбер?» Экстремальными графами для этого вопроса будут деревья с n вершинами, имеющие n − 1 рёбер^[2]. Более общий типичный вопрос следующий: Если дано свойство графа P, инвариант u^[3] и набор графов H, мы хотим найти минимальное значение m, такое, что любой граф из H, который имеет u, большее, чем m, обладает свойством P. В примере выше H было множеством графов с n вершинами, P было свойством быть циклом, а u было числом рёбер в графе. Таким образом, любой граф с n вершинами и более чем с n − 1 рёбрами, должен содержать цикл.

Некоторые функциональные результаты в экстремальной теории графов — это вопросы упомянутых выше видов. Например, на вопрос, как много рёбер графа с n вершинами должно быть в графе, чтобы он обязательно содержал в качестве подграфа клику размера k, отвечает теорема Турана. Если вместо клик в аналогичном вопросе спрашиваются о полных многодольных графах, ответ даёт теорема Эрдёша — Стоуна^[англ.].

Экстремальная теория графов возникла в 1941, когда Туран доказал свою теорему, определяющую графы порядка n, не содержащие полного графа K_k порядка k, и экстремальные относительно размера (то есть с как можно меньшим числом рёбер)^[4]. Следующим ключевым годом стал 1975, когда Семереди доказал свою теорему, важный инструмент для атаки на экстремальные задачи^[4].

Типичный результат экстремальной теории графов — теорема Турана. Теорема отвечает на следующий вопрос. Каково максимально возможное число рёбер в неориентированном графе G с n вершинами, не содержащем K₃ (три вершины A, B, C с рёбрами AB, AC, BC, то есть треугольник) в качестве подграфа? Полный двудольный граф, в котором доли отличаются максимум на 1, является единственным экстремальным графом с этим свойством. Граф содержит

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor }$

рёбер. Подобные вопросы ставились для различных других подграфов H вместо K₃. Например, задача Заранкиевича спрашивает о самом большом (по числу рёбер) графе, который не содержит фиксированного полного двудольного графа в качестве подграфа, а теорема о чётных контурах^[англ.] спрашивает о самом большом графе, не содержащем чётных циклов фиксированной длины. Туран также нашёл (уникальный) самый большой граф, не содержащий K_k, который назван его именем, а именно граф Турана. Этот граф является полным объединением "k-1" независимых множеств и имеет максимум

${\displaystyle \left\lfloor {\frac {(k-2)n^{2}}{2(k-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1}{k-1}}\right){\frac {n^{2}}{2}}\right\rfloor }$

рёбер. Наибольший граф с n вершинами, не содержащий C₄, имеет

${\displaystyle \left({\frac {1}{2}}+o(1)\right)n^{3/2}}$

рёбер.

Упомянутые теоремы дают условия для появления небольших объектов внутри (возможно) большого графа. В качестве противоположных экстремумов можно искать условие, которое вынуждает существование структуры, которая покрывает все вершины. Но граф с

${\displaystyle {\binom {n-1}{2}}}$

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

${\displaystyle \delta (G)=\min _{v\in G}d(v).}$

Задание большой минимальной степени удаляет возражение, что могут существовать «патологические» вершины. Если минимальная степень графа G равна 1, например, то не может быть изолированных вершин (даже если G содержит очень мало рёбер).

Классическим результатом является теорема Дирака, которая утверждает, что любой граф G с n вершинами и минимальной степенью, не меньшей n/2, содержит гамильтонов цикл.

• Теория Рамсея