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

Экстремальная теория графов это филиал математика который изучает, как глобальные свойства графа влияют на локальную подструктуру.^[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}$. Экстремальные примеры - деревья.

История

Теорема Мантеля (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) |}}$.

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

• Теория Рамсея
• Неравенства плотности графов
• Проблема запрещенного подграфа
• Зависимый случайный выбор

Примечания

Рекомендации

• Боллобаш, Бела (2004), Экстремальная теория графов, Нью-Йорк: Dover Publications, ISBN 978-0-486-43596-1.
• Боллобаш, Бела (1998), Современная теория графов, Берлин, Нью-Йорк: Springer-Verlag, стр. 103–144, ISBN 978-0-387-98491-9.
• Дистель, Рейнхард (2010), Теория графов (4-е изд.), Берлин, Нью-Йорк: Springer-Verlag, стр. 169–198, ISBN 978-3-642-14278-9, заархивировано из оригинал на 2017-05-28, получено 2013-11-18.
• М. Симоновиц, Слайды с лекций летней школы Чорина, 2006. [1]