Проблема с запрещенным подграфом

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

Эквивалентная проблема: сколько ребер в $n$-вершинный граф гарантирует, что в нем есть подграф, изоморфный $G$?

Определения

Экстремальное число $\operatorname {ex} (n,G)$ — максимальное количество ребер в $n$-вершинный граф, не содержащий подграфа, изоморфного $G$. $K_{r}$ это полный график на $r$ вершины. $T(n,r)$ — это граф Турана : полный $r$-дольный граф на $n$ вершины, причем вершины распределены между частями как можно более равномерно. Хроматическое число $\chi (G)$ из $G$ минимальное количество цветов, необходимое для раскраски вершин $G$ так, что никакие две соседние вершины не имеют одинакового цвета.

Верхние границы

Теорема Турана

Смотрите также: теорема Турана

Теорема Турана утверждает, что для натуральных чисел $n,r$ удовлетворяющий $n\geq r\geq 3$, ${\textstyle \operatorname {ex} (n,K_{r})=\left(1-{\frac {1}{r-1}}+o(1)\right){\frac {n^{2}}{2}}.}$

Это решает проблему запрещенного подграфа для $G=K_{r}$. Случаи равенства для теоремы Турана взяты из графа Турана. $T(n,r-1)$.

Этот результат можно обобщить на произвольные графы $G$ учитывая хроматическое число $\chi (G)$ из $G$. Обратите внимание, что $T(n,r)$ можно раскрасить с помощью $r$ цветов и, следовательно, не имеет подграфов с хроматическим числом больше, чем $r$. В частности, $T(n,\chi (G)-1)$ не имеет подграфов, изоморфных $G$. Это говорит о том, что общие случаи равенства для проблемы запрещенного подграфа могут быть связаны со случаями равенства для $G=K_{r}$. Эта интуиция оказывается верной, вплоть до $o(n^{2})$ ошибка.

Теорема Эрдеша – Стоуна

См. Также: теорема Эрдеша – Стоуна.

Теорема Эрдеша – Стоуна утверждает, что для всех натуральных чисел $n$ и все графики $G$, ${\textstyle \operatorname {ex} (n,G)=\left(1-{\frac {1}{\chi (G)-1}}+o(1)\right){\binom {n}{2}}.}$

Когда $G$ не является двудольным, это дает нам приближение первого порядка $\operatorname {ex} (n,G)$.

Двудольные графы

Для двудольных графов $G$, теорема Эрдеша – Стоуна говорит нам только, что $\operatorname {ex} (n,G)=o(n^{2})$. Проблема запрещенных подграфов для двудольных графов известна как проблема Заранкевича и в целом не решена.

Прогресс в решении проблемы Заранкевича включает следующую теорему:

Теорема Ковари–Соша–Турана. Для каждой пары натуральных чисел $s,t$ с $t\geq s\geq 1$, существует некоторая константа $C$ (независимо от $n$) такой, что ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ для каждого положительного целого числа $n$.

Другой результат для двудольных графов - это случай четных циклов: $G=C_{2k},k\geq 2$. Четные циклы обрабатываются путем рассмотрения корневой вершины и путей, ответвляющихся от этой вершины. Если два пути одинаковой длины $k$ имеют одну и ту же конечную точку и не перекрываются, то они создают цикл длины $2k$. Это дает следующую теорему.

Теорема ( Бонди и Симоновиц , 1974). Существует некоторая константа $C$ такой, что ${\textstyle \operatorname {ex} (n,C_{2k})\leq Cn^{1+{\frac {1}{k}}}}$ для каждого положительного целого числа $n$ и положительное целое число $k\geq 2$.

Мощная лемма экстремальной теории графов — зависимый случайный выбор . Эта лемма позволяет нам обрабатывать двудольные графы с ограниченной степенью в одной части:

Теорема ( Алон , Кривелевич и Судаков , 2003). Позволять $G$ быть двудольным графом с вершинными частями $A$ и $B$ такая, что каждая вершина в $A$ имеет высшее образование не более $r$. Тогда существует константа $C$ (зависит только от $G$) такой, что ${\textstyle \operatorname {ex} (n,G)\leq Cn^{2-{\frac {1}{r}}}}$для каждого положительного целого числа $n$.

В общем, у нас есть следующее предположение:

Гипотеза о рациональных показателях (Эрдёш и Симоновиц). Для любого конечного семейства ${\mathcal {L}}$ графов, если существует двудольный $L\in {\mathcal {L}}$, то существует рациональное $\alpha \in [0,1)$ такой, что $\operatorname {ex} (n,{\mathcal {L}})=\Theta (n^{1+\alpha })$.

Обзор Фюреди и Симоновица более подробно описывает прогресс в решении проблемы запрещенного подграфа.

Нижние границы

Для получения нижних оценок используются различные методы.

Вероятностный метод

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

Вероятностный метод можно использовать для доказательства. $\operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}$где $c$ является константой, зависящей только от графика $G$. Для построения можно взять случайный граф Эрдеша-Реньи $G(n,p)$, это график с $n$ вершины и ребро — это любые две вершины, нарисованные с вероятностью $p$, независимо. После вычисления ожидаемого количества копий $G$ в $G(n,p)$ по линейности ожидания мы удаляем одно ребро из каждой такой копии $G$ и у нас остается $G$-свободный граф в конце концов. Ожидаемое количество оставшихся ребер можно найти как $\operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}$ для постоянного $c$ в зависимости от $G$. Следовательно, хотя бы один $n$-граф вершин существует, по крайней мере, с таким количеством ребер, как ожидаемое число.

Этот метод можно использовать и для нахождения конструкций графа для границ обхвата графа. Обхват, обозначаемый $g(G)$, — длина кратчайшего цикла графа. Обратите внимание, что для $g(G)>2k$, граф должен запрещать все циклы длиной меньше, чем равна $2k$. По линейности ожидания ожидаемое количество таких запрещенных циклов равно сумме ожидаемого числа циклов. $C_{i}$ (для $i=3,...,n-1,n$.). Мы снова удаляем ребра из каждой копии запрещенного графа и в итоге получаем граф, свободный от меньших циклов и $g(G)>2k$, давая нам $c_{0}n^{1+{\frac {1}{2k-1}}}$ ребра в графе слева.

Алгебраические конструкции

Для конкретных случаев были внесены улучшения за счет нахождения алгебраических конструкций. Общей чертой таких конструкций является то, что они включают использование геометрии для построения графа, вершины которого представляют геометрические объекты, а ребра — в соответствии с алгебраическими отношениями между вершинами. В итоге у нас нет подграфа $G$, исключительно по чисто геометрическим причинам, в то время как граф имеет большое количество ребер, что делает его строгой границей из-за способа определения инцидентностей. Следующее доказательство Эрдеша, Реньи и Соша установление нижней границы $\operatorname {ex} (n,K_{2,2})$ как $\left({\frac {1}{2}}-o(1)\right)n^{3/2}.$, демонстрирует мощь этого метода.

Во-первых, предположим, что $n=p^{2}-1$ для какого-то премьера $p$. Рассмотрим график полярности $G$ с элементами вершин $\mathbb {F} _{p}^{2}-\{0,0\}$ и ребра между вершинами $(x,y)$ и $(a,b)$ тогда и только тогда, когда $ax+by=1$ в $\mathbb {F} _{p}$. Этот график $K_{2,2}$-свободно, поскольку система двух линейных уравнений в $\mathbb {F} _{p}$ не может иметь более одного решения. Вершина $(a,b)$ (предполагать $b\neq 0$) подключен к $\left(x,{\frac {1-ax}{b}}\right)$ для любого $x\in \mathbb {F} _{p}$, в общей сложности не менее $p-1$ ребра (вычитается 1 в случае, если $(a,b)=\left(x,{\frac {1-ax}{b}}\right)$). Так что есть как минимум ${\frac {1}{2}}(p^{2}-1)(p-1)=\left({\frac {1}{2}}-o(1)\right)p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{3/2}$ края по желанию. Для общего $n$, мы можем взять $p=(1-o(1)){\sqrt {n}}$ с $p\leq {\sqrt {n+1}}$ (что возможно, поскольку существует простое число $p$ в интервале $[k-k^{0.525},k]$ для достаточно большого $k$) и построим граф полярности, используя такой $p$, затем добавив $n-p^{2}+1$ изолированные вершины, не влияющие на асимптотическое значение.

Следующая теорема представляет собой аналогичный результат для $K_{3,3}$.

Теорема (Браун, 1966). $\operatorname {ex} (n,K_{3,3})\geq \left({\frac {1}{2}}-o(1)\right)n^{5/3}.$

Схема доказательства. Как и в предыдущей теореме, мы можем взять $n=p^{3}$ для премьер-министра $p$ и пусть вершины нашего графа являются элементами $\mathbb {F} _{p}^{3}$. На этот раз вершины $(a,b,c)$ и $(x,y,z)$ связаны тогда и только тогда, когда $(x-a)^{2}+(y-b)^{2}+(z-c)^{2}=u$ в $\mathbb {F} _{p}$, для некоторых специально выбранных $u$. Тогда это $K_{3,3}$-свободно, поскольку не более двух точек лежат на пересечении трех сфер. Тогда, поскольку значение $(x-a)^{2}+(y-b)^{2}+(z-c)^{2}$ почти однороден по всему $\mathbb {F} _{p}$, каждая точка должна иметь около $p^{2}$ ребер, поэтому общее количество ребер равно $\left({\frac {1}{2}}-o(1)\right)p^{2}\cdot p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{5/3}$.

Однако остается открытым вопрос об ужесточении нижней границы для $\operatorname {ex} (n,K_{t,t})$ для $t\geq 4$.

Теорема (Алон и др., 1999) Для $t\geq (s-1)!+1$, $\operatorname {ex} (n,K_{s,t})=\Theta (n^{2-{\frac {1}{s}}}).$

Рандомизированные алгебраические конструкции

Этот метод сочетает в себе две вышеупомянутые идеи. Он использует отношения случайного полиномиального типа при определении инцидентности между вершинами, которые находятся в некотором алгебраическом множестве. Используя этот прием, докажите следующую теорему.

Теорема : Для каждого $s\geq 2$, существует некоторый $t$ такой, что $\operatorname {ex} (n,K_{s,t})\geq \left({\frac {1}{2}}-o(1)\right)n^{2-{\frac {1}{s}}}$.

Схема доказательства: возьмем наибольшую степень простого числа. $q$ с $q^{s}\leq n$. Благодаря простым пробелам имеем $q=(1-o(1))n^{\frac {1}{s}}$. Позволять $f\in \mathbb {F} _{q}[x_{1},x_{2},\cdots ,x_{s},y_{1},y_{2},\cdots ,y_{s}]_{\leq d}$ быть случайным многочленом от $\mathbb {F} _{q}$ со степенью максимум $d=s^{2}$ в $X=(X_{1},X_{2},...,X_{s})$ и $Y=(Y_{1},Y_{2},...,Y_{s})$ и удовлетворение $f(X,Y)=f(Y,X)$. Пусть граф $G$ иметь набор вершин $\mathbb {F} _{q}^{s}$ такие, что две вершины $x,y$ являются соседними, если $f(x,y)=0$.

Мы чиним комплект $U\subset \mathbb {F} _{q}^{s}$и определение набора $Z_{U}$ как элементы $\mathbb {F} _{q}^{s}$ не в $U$ удовлетворяющий $f(x,u)=0$ для всех элементов $u\in U$. Используя оценку Ланга–Вейля, получаем, что для $q$ достаточно большой, мы имеем $|Z_{U}|\leq C$ или $|Z_{U}|>{\frac {q}{2}}$ для некоторой константы $C$.Теперь мы вычисляем ожидаемое количество $U$ такой, что $Z_{U}$ имеет размер больше, чем $C$и удаляем из каждого такого вершину $U$. Полученный график оказывается $K_{s,C+1}$ свободен, и существует хотя бы один граф с ожидаемым количеством ребер этого результирующего графа.

Пересыщение

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

Плотность Турана

Плотность Турана $h$-однородный граф $G$ определяется как

$\pi (G)=\lim _{n\to \infty }{\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}.$

Это правда, что ${\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}$ на самом деле положительна и монотонно убывает, поэтому предел должен существовать.

В качестве примера теорема Турана дает следующее: $\pi (K_{r+1})=1-{\frac {1}{r}}$, а теорема Эрдеша – Стоуна дает, что $\pi (G)=1-{\frac {1}{\chi (H)-1}}$. В частности, для двустороннего $G$, $\pi (G)=0$. Определение плотности Турана $\pi (H)$ эквивалентно определению $\operatorname {ex} (n,G)$ до $o(n^{2})$ ошибка.

Теорема о пересыщении

Рассмотрим $h$-однородный гиперграф $H$ с $v(H)$ вершины. Теорема о пересыщении утверждает, что для каждого $\epsilon >0$, существует $\delta >0$ такое, что если $G$ это $h$-однородный гиперграф на $n$ вершины и по крайней мере $(\pi (H)+\epsilon ){\binom {n}{h}}$ края для $n$ достаточно велики, то существует по крайней мере $\delta n^{v(H)}$ копии $H$.

Эквивалентно, мы можем переформулировать эту теорему следующим образом: если граф $G$ с $n$ вершин имеет $o(n^{v(H)})$ копии $H$, то существует не более $\pi (H){\binom {n}{2}}+o(n^{2})$ края в $G$.

Приложения

Мы можем решить различные проблемы запрещенного подграфа, рассматривая проблемы типа пересыщения. Ниже мы переформулируем и приведем схему доказательства теоремы Ковари – Соша – Турана:

Теорема Ковари–Соша–Турана. Для каждой пары натуральных чисел $s,t$ с $t\geq s\geq 1$, существует некоторая константа $C$ (независимо от $n$) такой, что ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ для каждого положительного целого числа $n$.

Доказательство. Позволять $G$ быть $2$-график на $n$ вершин и учтите количество копий $K_{1,s}$ в $G$. Дана вершина степени $d$, мы получаем ровно ${\binom {d}{s}}$ копии $K_{1,s}$ с корнем в этой вершине, всего $\sum _{v\in V(G)}{\binom {\operatorname {deg} (v)}{s}}$ копии. Здесь, ${\binom {k}{s}}=0$ когда $0\leq k<s$. По выпуклости всего существует не менее $n{\binom {2e(G)/n}{s}}$ копии $K_{1,s}$. Более того, существуют явно ${\binom {n}{s}}$ подмножества $s$ вершин, поэтому, если их больше, чем $(t-1){\binom {n}{s}}$ копии $K_{1,s}$, то согласно принципу голубиного отверстия должно существовать подмножество $s$ вершины, образующие множество листьев не менее $t$ этих копий, образуя $K_{s,t}$. Таким образом, имеет место возникновение $K_{s,t}$ пока у нас есть $n{\binom {2e(G)/n}{s}}>(t-1){\binom {n}{s}}$. Другими словами, мы имеем вхождение, если ${\frac {e(G)^{s}}{n^{s-1}}}\geq O(n^{s})$, что упрощает $e(G)\geq O(n^{2-{\frac {1}{s}}})$, что является утверждением теоремы.

В этом доказательстве мы используем метод пересыщения, рассматривая количество вхождений меньшего подграфа. Обычно в приложениях метода пересыщения теорема о пересыщении не используется. Вместо этого структура часто включает в себя поиск подграфа $H'$ какого-то запрещенного подграфа $H$ и показывая, что если оно появляется слишком много раз в $G$, затем $H$ должен появиться в $G$ также. Другие теоремы, касающиеся проблемы запрещенного подграфа, которую можно решить с помощью пересыщения, включают:

• $\operatorname {ex} (n,C_{2t})\leq O(n^{1+1/t})$.
• Для любого $t$ и $k\geq 2$, $\operatorname {ex} (n,C_{2k},C_{2k-1})\leq O\left(\left({\frac {n}{2}}\right)^{1+1/t}\right)$.
• Если $Q$ обозначает граф, определяемый вершинами и ребрами куба, а $Q^{*}$ обозначает граф, полученный соединением двух противоположных вершин куба, тогда $\operatorname {ex} (n,Q)\leq \operatorname {ex} (n,Q^{*})=O(n^{8/5})$.

Обобщения

Проблему можно обобщить для набора запрещенных подграфов. $S$: найти максимальное количество ребер в $n$-вершинный граф, не имеющий подграфа, изоморфного любому графу из $S$.

Существуют также с гиперграфами гораздо более сложные версии задач о запрещенных подграфах . Например, задачу Турана можно обобщить до запроса наибольшего числа ребер в $n$-вершинный 3-однородный гиперграф, не содержащий тетраэдров. Аналогом конструкции Турана было бы разбиение вершин на почти равные подмножества. $V_{1},V_{2},V_{3}$, и соедините вершины $x,y,z$ на 3-ребро, если они все в разных $V_{i}$s, или если двое из них находятся в $V_{i}$ и третий находится внутри $V_{i+1}$ (где $V_{4}=V_{1}$). Он не содержит тетраэдров, а плотность ребер равна $5/9$. Однако наиболее известная верхняя граница равна 0,562, если использовать технику алгебр флагов.

См. также

• Граф без биклик
• Гипотеза Эрдеша – Хайнала
• Номер Турана
• Проблема изоморфизма подграфов
• Запрещенная характеристика графа