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

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

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

История [ править ]

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

Пупс (2004) ^[3]

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

Темы и концепции [ править ]

Раскраска графика [ править ]

Правильная (вершинная) раскраска графа $G$ это раскраска вершин $G$ так, что никакие две соседние вершины не имеют одинакового цвета. Минимальное количество цветов, необходимое для правильного окрашивания. $G$ называется хроматическим числом $G$ , обозначенный $\chi (G)$ . Определение хроматического числа конкретных графов является фундаментальным вопросом экстремальной теории графов, поскольку многие задачи в этой и смежных областях можно сформулировать в терминах раскраски графов. ^[2]

Две простые нижние оценки хроматического числа графа $G$ определяется номером клики $\omega (G)$ — все вершины клики должны иметь разные цвета — и $|V(G)|/\alpha (G)$ , где $\alpha (G)$ — число независимости, поскольку набор вершин данного цвета должен образовывать независимый набор .

Жадная раскраска дает верхнюю границу $\chi (G)\leq \Delta (G)+1$ , где $\Delta (G)$ это максимальная степень $G$ . Когда $G$ не является нечетным циклом или кликой, теорема Брукса утверждает, что верхняя оценка может быть сведена к $\Delta (G)$ . Когда $G$ является плоским графом , теорема о четырех цветах утверждает, что $G$ имеет хроматическое число не более четырех.

В общем случае определение того, имеет ли данный граф раскраску в заданное количество цветов, как известно, является NP-трудной задачей .

Помимо раскраски вершин изучаются и другие виды раскраски, например раскраски ребер . Хроматический индекс $\chi '(G)$ графика $G$ - минимальное количество цветов в правильной раскраске ребер графа, а теорема Визинга утверждает, что хроматический индекс графа $G$ либо $\Delta (G)$ или $\Delta (G)+1$ .

Запрещенные подграфы [ править ]

Проблема запрещенного подграфа является одной из центральных проблем экстремальной теории графов. Учитывая график $G$ , проблема запрещенного подграфа требует максимального количества ребер $\operatorname {ex} (n,G)$ в $n$ -вершинный граф, не содержащий подграфа, изоморфного $G$ .

Когда $G=K_{r}$ является полным графом, теорема Турана дает точное значение для $\operatorname {ex} (n,K_{r})$ и характеризует все графы, достигающие этого максимума; такие графы известны как графы Турана . Для недвудольных графов $G$ , теорема Эрдеша – Стоуна дает асимптотическое значение $\operatorname {ex} (n,G)$ по хроматическому числу $G$ . Задача определения асимптотики $\operatorname {ex} (n,G)$ когда $G$ – двудольный граф открыт; когда $G$ является полным двудольным графом, это известно как проблема Заранкевича .

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

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

Проблему запрещенного подграфа можно переформулировать как максимизацию плотности ребер графа с $G$ -плотность равна нулю, и это естественным образом приводит к обобщению в виде неравенств гомоморфизма графов , которые представляют собой неравенства, связывающие $t(H,G)$ для различных графиков $H$ .Распространив плотность гомоморфизма на графоны , которые являются объектами, возникающими как предел плотных графов , плотность гомоморфизма графа можно записать в виде интегралов, а такие неравенства, как неравенство Коши-Шварца и неравенство Гёльдера, можно использовать для вывода неравенства гомоморфизма.

Основной открытой проблемой, связанной с плотностями гомоморфизма, является гипотеза Сидоренко , которая устанавливает точную нижнюю оценку плотности гомоморфизма двудольного графа в графе. $G$ с точки зрения краевой плотности $G$ .

Регулярность графика [ править ]

Лемма Семереди о регулярности утверждает, что все графы «регулярны» в следующем смысле: множество вершин любого данного графа можно разделить на ограниченное число частей так, что двудольный граф между большинством пар частей ведет себя как случайные двудольные графы . ^[2]Это разделение дает структурную аппроксимацию исходного графа, которая раскрывает информацию о свойствах исходного графа.

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

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

См. также [ править ]

Связанные поля

Техники и методы

Теоремы и гипотезы (помимо упомянутых выше)

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Дистель, Рейнхард (2010), Теория графов (4-е изд.), Берлин, Нью-Йорк: Springer-Verlag, стр. 169–198, ISBN 978-3-642-14278-9 , заархивировано из оригинала 28 мая 2017 г. , получено 18 ноября 2013 г.
^ Jump up to: Перейти обратно: ^а ^б ^с Алон, Нога ; Кривелевич, Михаил (2008). «Экстремальная и вероятностная комбинаторика». В Гауэрсе, Тимоти ; Барроу-Грин, июнь ; Лидер, Имре (ред.). Принстонский спутник математики . Принстон, Нью-Джерси : Издательство Принстонского университета . стр. 562–575. дои : 10.1515/9781400830398 . ISBN 978-0-691-11880-2 . JSTOR j.ctt7sd01 . LCCN 2008020450 . МР 2467561 . OCLC 227205932 . ОЛ 19327100М . Збл 1242.00016 .
^ Боллобас, Бела (2004), Экстремальная теория графов , Нью-Йорк: Dover Publications , ISBN 978-0-486-43596-1
^ Jump up to: Перейти обратно: ^а ^б Боллобас, Бела (1998), Современная теория графов , Берлин, Нью-Йорк: Springer-Verlag , стр. 103–144, ISBN 978-0-387-98491-9

[:0-1] Jump up to: Перейти обратно: ^а ^б Дистель, Рейнхард (2010), Теория графов (4-е изд.), Берлин, Нью-Йорк: Springer-Verlag, стр. 169–198, ISBN 978-3-642-14278-9 , заархивировано из оригинала 28 мая 2017 г. , получено 18 ноября 2013 г.

[pcm-2] Jump up to: Перейти обратно: ^а ^б ^с Алон, Нога ; Кривелевич, Михаил (2008). «Экстремальная и вероятностная комбинаторика». В Гауэрсе, Тимоти ; Барроу-Грин, июнь ; Лидер, Имре (ред.). Принстонский спутник математики . Принстон, Нью-Джерси : Издательство Принстонского университета . стр. 562–575. дои : 10.1515/9781400830398 . ISBN 978-0-691-11880-2 . JSTOR j.ctt7sd01 . LCCN 2008020450 . МР 2467561 . OCLC 227205932 . ОЛ 19327100М . Збл 1242.00016 .

[3] Боллобас, Бела (2004), Экстремальная теория графов , Нью-Йорк: Dover Publications , ISBN 978-0-486-43596-1

[b104-4] Jump up to: Перейти обратно: ^а ^б Боллобас, Бела (1998), Современная теория графов , Берлин, Нью-Йорк: Springer-Verlag , стр. 103–144, ISBN 978-0-387-98491-9

[1]

[2]

[3]

[4]