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

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

В График Турана Т(п,р) является примером экстремального графа. Он имеет максимально возможное количество ребер для графа на п вершины без (р + 1)-клики. Это Т(13,4).

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

Примеры

Теория экстремальных графов может быть мотивирована такими вопросами, как:

Вопрос 1. Какое максимально возможное количество ребер в графе на ${ displaystyle n}$ вершины такие, что не содержат цикла?

Если график на ${ displaystyle n}$ вершин содержит не менее ${ displaystyle n}$ ребра, то он тоже должен содержать цикл. Более того, любые дерево с ${ displaystyle n}$ вершины содержат ${ displaystyle n-1}$ ребра и не содержит циклов; деревья - единственные графы с ${ displaystyle n-1}$ ребра и без циклов. Следовательно, ответ на этот вопрос ${ displaystyle n-1}$ , а деревья - экстремальные графы.^[2]

Вопрос 2. Если график на ${ displaystyle n}$ vertices не содержит подграфа треугольника, какое максимальное количество ребер он может иметь?

Теорема Мантеля отвечает на этот вопрос - максимальное количество ребер ${ Displaystyle lfloor п ^ {2} / 4 rfloor}$ . Соответствующий экстремальный граф - это полный двудольный граф на ${ Displaystyle ( lceil п / 2 rceil, lfloor n / 2 rfloor)}$ вершины, то есть две части различаются размером не более чем на 1.

Далее следует обобщение вопроса 2:

Вопрос 3. Позволять ${ displaystyle r}$ быть положительным целым числом. Сколько ребер должно быть в графе ${ displaystyle G}$ на ${ displaystyle n}$ вершины, чтобы гарантировать, что независимо от того, как расположены ребра, клика ${ displaystyle K_ {r}}$ можно найти как подграф?

Ответ на этот вопрос ${ displaystyle { frac {r-2} {r-1}} cdot { frac {n ^ {2}} {2}} + 1}$ и на него отвечает Теорема Турана. Следовательно, если граф ${ displaystyle G}$ на ${ displaystyle n}$ вершины ${ displaystyle K_ {r}}$ -бесплатно, может иметь самое большее ${ Displaystyle left lfloor { frac {(r-2) n ^ {2}} {2 (r-1)}} right rfloor = left lfloor left (1 - { frac {1) } {r-1}} right) { frac {n ^ {2}} {2}} right rfloor}$

много краев; соответствующий экстремальный граф с таким количеством ребер является График Турана, показанный на рисунке выше. Это полное соединение из ${ displaystyle r-1}$ независимые множества (с максимально равными размерами - такое разбиение называется справедливый).

Следующий вопрос является обобщением вопроса 3, где полный граф ${ displaystyle K_ {r}}$ заменяется любым графом ${ displaystyle H}$ :

Вопрос 4. Позволять ${ displaystyle r}$ быть положительным целым числом, и ${ displaystyle H}$ любой график на ${ displaystyle r}$ вершины. Сколько ребер должно быть в графе ${ displaystyle G}$ на ${ displaystyle n}$ вершин, чтобы гарантировать, что независимо от того, как расположены ребра, ${ displaystyle H}$ является подграфом ${ displaystyle G}$ ?

На этот вопрос в основном отвечает Теорема Эрдеша – Стоуна. Главный нюанс - для двудольных ${ displaystyle H}$ , теорема не дает удовлетворительного определения асимптотики экстремального числа ребер. Для многих конкретных (классов) двудольных графов определение асимптотики остается открытой проблемой.

Несколько основополагающих результатов в экстремальной теории графов отвечают на вопросы, которые следуют этой общей формулировке:

Вопрос 5. Учитывая свойство графа ${ displaystyle P}$ , параметр ${ Displaystyle и = и (G)}$ описание графа, и набор графов ${ Displaystyle { mathcal {S}}}$ , мы хотим найти минимально возможное значение ${ displaystyle u_ {0}}$ такой, что каждый граф ${ Displaystyle G in { mathcal {S}}}$ с ${ Displaystyle и (G) geq и_ {0}}$ имеет собственность ${ displaystyle P}$ . Кроме того, мы можем захотеть описать графики ${ displaystyle G}$ которые являются экстремальными в смысле наличия ${ Displaystyle и (G)}$ рядом с ${ displaystyle u_ {0}}$ но которые не удовлетворяют свойству ${ displaystyle P}$ .

В вопросе 1, например, ${ Displaystyle { mathcal {S}}}$ это набор ${ displaystyle n}$ -вершинные графы, ${ displaystyle P}$ свойство содержать цикл, ${ displaystyle u}$ - количество ребер, а обрезка ${ displaystyle u_ {0} = n}$ . Экстремальные примеры - деревья.

История

Теория экстремальных графов в самом строгом смысле слова - это раздел теории графов, развитый и любимый венграми.

Боллобаш (2004)

Теорема Мантеля (1907 г.) и Теорема Турана (1941) были одними из первых вех в изучении экстремальной теории графов.^[3] В частности, теорема Турана позже стала мотивацией для получения таких результатов, как Теорема Эрдеша-Стоуна-Симоновица (1946).^[1] Этот результат удивителен, потому что он связывает хроматическое число с максимальным количеством ребер в ${ displaystyle H}$ -свободный граф. Альтернативное доказательство Эрдёша-Стоуна-Симоновица было дано в 1975 году и использовало Лемма Семереди о регулярности, важный метод решения экстремальных задач теории графов.^[3]

Результаты плотности и неравенства

Глобальный параметр, который играет важную роль в экстремальной теории графов, - это плотность подграфов; для графика ${ Displaystyle G = (V, E)}$ и график ${ displaystyle H}$ , его плотность подграфа определяется как

${ displaystyle t (H, G) = ({ text {количество копий}} H { text {in}} G) / { binom {n} {| V (H) |}}}$ .

В частности, плотность краев - это плотность подграфов для ${ displaystyle H = K_ {2}}$ :

${ Displaystyle т (К_ {2}, G) = | E | / { binom {| V |} {2}}}$

Упомянутые выше теоремы можно перефразировать в терминах плотности краев. Например, Теорема Мантеля следует, что плотность ребер подграфа без треугольников не превосходит ${ displaystyle 1/2}$ . Теорема Турана означает, что плотность ребер ${ displaystyle K_ {r}}$ -свободный граф не более ${ Displaystyle (г-2 / г-1) + о (1)}$ .

Более того, теорема Эрдеша-Стоуна-Симоновица утверждает, что

${ displaystyle { mbox {ex}} (n; H) = left (1 - { frac {1} { chi (H) -1}} + o (1) right) {n select 2 },}$

куда ${ Displaystyle бывший (п; Н)}$ - максимальное количество ребер, на которых ${ displaystyle H}$ -свободный график на ${ displaystyle n}$ вершины могут иметь, и ${ Displaystyle чи (Н)}$ это хроматическое число из ${ displaystyle H}$ . Интерпретация этого результата состоит в том, что плотность края ${ displaystyle H}$ -свободный граф асимптотически ${ Displaystyle 1- (1 / ( чи (H) -1))}$ .

Другой результат Эрдёш, Реньи и Сош (1966) показывает, что график на ${ displaystyle n}$ вершины, не содержащие ${ displaystyle C_ {4}}$ поскольку подграф имеет не более следующего числа ребер.

${ Displaystyle влево ({ гидроразрыва {1} {2}} + о (1) вправо) п ^ {3/2}}$

Условия минимальной степени

Сформулированные выше теоремы дают условия для появления небольшого объекта внутри (возможно) очень большого графа. Другое направление в экстремальной теории графов - поиск условий, гарантирующих существование структуры, покрывающей каждую вершину. Обратите внимание, что это возможно даже для графика с ${ displaystyle n}$ вершины и ${ Displaystyle { binom {п-1} {2}}}$ ребра должны иметь изолированную вершину, даже если в графе присутствуют почти все возможные ребра. Условия подсчета ребер не указывают, как распределяются ребра в графе, что приводит к результатам, которые обнаруживают только ограниченные структуры на очень больших графах. Это дает мотивацию для рассмотрения параметра минимальной степени, который определяется как

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

Большая минимальная степень исключает возможность наличия некоторых «патологических» вершин; если минимальная степень графа грамм равно 1, то изолированных вершин быть не может (даже если грамм может иметь очень мало краев).

Результат экстремальной теории графов, связанный с параметром минимальной степени: Теорема Дирака, который утверждает, что каждый граф ${ displaystyle G}$ с ${ displaystyle n}$ вершины и минимальная степень не менее ${ displaystyle n / 2}$ содержит Цикл Гамильтона.

Другая теорема^[3] говорит, что если минимальная степень графа ${ displaystyle G}$ является ${ displaystyle delta geq 3}$ , а обхват ${ displaystyle g geq 3}$ , то количество вершин в графе не менее

${ displaystyle n_ {0} ( delta, g) = { begin {cases} 1 + { frac { delta} { delta -2}} [( delta -1) ^ {(g-1) / 2} -1] & { text {if}} g { text {is odd}} { frac {2} { delta -2}} [( delta -1) ^ {g / 2 } -1] & { text {if}} g { text {четно}} end {case}}}$ .

Некоторые открытые вопросы

Несмотря на то, что в области экстремальной теории графов было сделано много важных наблюдений, некоторые вопросы все еще остаются без ответа. Например, Проблема заранкевича спрашивает, каково максимально возможное количество ребер в двудольный граф на ${ displaystyle n}$ вершины, которые не имеют полный двудольный подграфы размера ${ displaystyle m}$ .

Другая важная гипотеза в экстремальной теории графов была сформулирована Сидоренко в 1993 г.. Предполагается, что если ${ displaystyle H}$ является двудольным графом, то его графон плотность (обобщенное понятие плотности графа) ${ displaystyle t (H, W)}$ по крайней мере ${ Displaystyle т (К_ {2}, W) ^ {| v (H) |}}$ .

Смотрите также

Примечания

^ ^а ^б Diestel 2010
^ Bollobás 2004, п. 9
^ ^а ^б ^c Боллобаш 1998, п. 104