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

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

Эквивалентная задача — сколько ребер в графе с вершинами гарантируют, что у него есть подграф, изоморфный ? [2] н {\displaystyle n} Г {\displaystyle G}

Определения

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

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

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

Теорема Турана утверждает, что для положительных целых чисел, удовлетворяющих , [3] н , г {\displaystyle н,р} н ≥ г ≥ 3 {\displaystyle n\geq r\geq 3} бывший ⁡ ( н , К г ) = ( 1 − 1 г − 1 + о ( 1 ) ) н 2 2 . {\textstyle \operatorname {ex} (n,K_{r})=\left(1-{\frac {1}{r-1}}+o(1)\right){\frac {n^{2}}{2}}.}

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

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

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

Теорема Эрдеша–Стоуна утверждает, что для всех положительных целых чисел и всех графов [4] н {\displaystyle n} Г {\displaystyle G} бывший ⁡ ( н , Г ) = ( 1 − 1 χ ( Г ) − 1 + о ( 1 ) ) ( н 2 ) . {\textstyle \operatorname {ex} (n,G)=\left(1-{\frac {1}{\chi (G)-1}}+o(1)\right){\binom {n}{2}}.}

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

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

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

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

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

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

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

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

Теорема ( Алон , Кривелевич и Судаков , 2003). Пусть — двудольный граф с вершинными частями и такой, что каждая вершина в имеет степень не более . Тогда существует константа (зависящая только от ) такая, что для любого положительного целого числа . [7] Г {\displaystyle G} А {\displaystyle А} Б {\displaystyle Б} А {\displaystyle А} г {\displaystyle r} С {\displaystyle С} Г {\displaystyle G} бывший ⁡ ( н , Г ) ≤ С н 2 − 1 г {\textstyle \operatorname {ex} (n,G)\leq Cn^{2-{\frac {1}{r}}}} н {\displaystyle n}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема (Алон и др., 1999) Для , [14] t ≥ ( s − 1 ) ! + 1 {\displaystyle t\geq (s-1)!+1} ex ⁡ ( n , K s , t ) = Θ ( n 2 − 1 s ) . {\displaystyle \operatorname {ex} (n,K_{s,t})=\Theta (n^{2-{\frac {1}{s}}}).}

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

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

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

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

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

Пересыщение

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

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

Плотность Турана -однородного графа определяется как h {\displaystyle h} G {\displaystyle G}

π ( G ) = lim n → ∞ ex ⁡ ( n , G ) ( n h ) . {\displaystyle \pi (G)=\lim _{n\to \infty }{\frac {\operatorname {ex} (n,G)}{\binom {n}{h}}}.}

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


Например, теорема Турана дает, что , а теорема Эрдёша–Стоуна дает, что . В частности, для двудольного , . Определение плотности Турана эквивалентно определению с точностью до ошибки. [16] π ( K r + 1 ) = 1 − 1 r {\displaystyle \pi (K_{r+1})=1-{\frac {1}{r}}} π ( G ) = 1 − 1 χ ( H ) − 1 {\displaystyle \pi (G)=1-{\frac {1}{\chi (H)-1}}} G {\displaystyle G} π ( G ) = 0 {\displaystyle \pi (G)=0} π ( H ) {\displaystyle \pi (H)} ex ⁡ ( n , G ) {\displaystyle \operatorname {ex} (n,G)} o ( n 2 ) {\displaystyle o(n^{2})}

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

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

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

Приложения

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

Теорема Ковари–Шоша–Турана. Для каждой пары положительных целых чисел с , существует некоторая константа (независимая от ), такая что для каждого положительного целого числа . [18] s , t {\displaystyle s,t} t ≥ s ≥ 1 {\displaystyle t\geq s\geq 1} C {\displaystyle C} n {\displaystyle n} ex ⁡ ( n , K s , t ) ≤ C n 2 − 1 s {\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}} n {\displaystyle n}
Доказательство. Пусть будет -графом на вершинах, и рассмотрим количество копий в . При заданной вершине степени мы получаем ровно копий с корнем в этой вершине, всего копий. Здесь, когда . По выпуклости, всего имеется не менее копий . Более того, очевидно, что существуют подмножества вершин, поэтому если имеется более копий , то по принципу Пиджеонхола должно существовать подмножество вершин, которые образуют множество листьев не менее этих копий, образуя . Следовательно, существует вхождение , пока у нас есть . Другими словами, у нас есть вхождение , если , что упрощается до , что является утверждением теоремы. [19] G {\displaystyle G} 2 {\displaystyle 2} n {\displaystyle n} K 1 , s {\displaystyle K_{1,s}} G {\displaystyle G} d {\displaystyle d} ( d s ) {\displaystyle {\binom {d}{s}}} K 1 , s {\displaystyle K_{1,s}} ∑ v ∈ V ( G ) ( deg ⁡ ( v ) s ) {\displaystyle \sum _{v\in V(G)}{\binom {\operatorname {deg} (v)}{s}}} ( k s ) = 0 {\displaystyle {\binom {k}{s}}=0} 0 ≤ k < s {\displaystyle 0\leq k<s} n ( 2 e ( G ) / n s ) {\displaystyle n{\binom {2e(G)/n}{s}}} K 1 , s {\displaystyle K_{1,s}} ( n s ) {\displaystyle {\binom {n}{s}}} s {\displaystyle s} ( t − 1 ) ( n s ) {\displaystyle (t-1){\binom {n}{s}}} K 1 , s {\displaystyle K_{1,s}} s {\displaystyle s} t {\displaystyle t} K s , t {\displaystyle K_{s,t}} K s , t {\displaystyle K_{s,t}} n ( 2 e ( G ) / n s ) > ( t − 1 ) ( n s ) {\displaystyle n{\binom {2e(G)/n}{s}}>(t-1){\binom {n}{s}}} e ( G ) s n s − 1 ≥ O ( n s ) {\displaystyle {\frac {e(G)^{s}}{n^{s-1}}}\geq O(n^{s})} e ( G ) ≥ O ( n 2 − 1 s ) {\displaystyle e(G)\geq O(n^{2-{\frac {1}{s}}})}

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

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

Обобщения

Задача может быть обобщена для множества запрещенных подграфов : найти максимальное число ребер в -вершинном графе, который не имеет подграфа, изоморфного ни одному графу из . [21] S {\displaystyle S} n {\displaystyle n} S {\displaystyle S}

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

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

Ссылки

  1. ^ Комбинаторика: системы множеств, гиперграфы, семейства векторов и вероятностная комбинаторика , Бела Боллобаш , 1986, ISBN  0-521-33703-8 , стр. 53, 54
  2. ^ «Современная теория графов», Бела Боллобас, 1998, ISBN 0-387-98488-7 , стр. 103 
  3. ^ Туран, Пал (1941). «Об одной экстремальной задаче теории графов». Matematikai és Fizikai Lapok (на венгерском языке). 48 : 436–452 .
  4. ^ Эрдёш, П.; Стоун , А. Х. (1946). «О структуре линейных графов» (PDF) . Бюллетень Американского математического общества . 52 (12): 1087– 1091. doi : 10.1090/S0002-9904-1946-08715-7 .
  5. ^ Ковари, Т.; Т. Сос, В .; Туран, П. (1954), «К проблеме К. Заранкевича» (PDF) , Colloq. Математика. , 3 : 50–57 , doi : 10,4064/см-3-1-50-57 , MR  0065617
  6. ^ Бонди, JA ; Симоновиц, М. (апрель 1974 г.). «Циклы четной длины в графах». Журнал комбинаторной теории . Серия B. 16 (2): 97– 105. doi : 10.1016/0095-8956(74)90052-5 . MR  0340095.
  7. ^ Алон, Нога ; Кривелевич, Майкл ; Судаков, Бенни . "Числа Турана двудольных графов и связанные с ними вопросы типа Рамсея". Комбинаторика, вероятность и вычисления . MR  2037065.
  8. ^ аб Фюреди, Золтан; Симоновиц, Миклош (21 июня 2013 г.). «История вырожденных (двудольных) экстремальных задач на графах». arXiv : 1306,5167 [math.CO].
  9. ^ Чжао , Юфэй. «Теория графов и аддитивная комбинаторика» (PDF) . стр.  32–37 . Получено 2 декабря 2019 г.
  10. ^ Эрдеш, П.; Реньи, А.; Сос, В.Т. (1966). «К одной задаче теории графов». Студия Sci. Математика. Венгрия. 1 : 215–235 . МР  0223262.
  11. ^ Бейкер, RC; Харман, G.; Пинц, J. (2001), "Разница между последовательными простыми числами. II.", Proc. London Math. Soc. , Series 3, 83 (3): 532– 562, doi :10.1112/plms/83.3.532, MR  1851081, S2CID  8964027
  12. ^ Браун, WG (1966). «О графах, не содержащих граф Томсена». Canad. Math. Bull. 9 (3): 281– 285. doi : 10.4153/CMB-1966-036-2 . MR  0200182.
  13. ^ Чжао , Юфэй. «Теория графов и аддитивная комбинаторика» (PDF) . стр.  32–37 . Получено 2 декабря 2019 г.
  14. ^ Алон, Нога; Роньяи, Лайош; Сабо, Тибор (1999). «Норм-графы: вариации и приложения». Журнал комбинаторной теории . Серия B. 76 (2): 280–290 . doi : 10.1006/jctb.1999.1906 . MR  1699238.
  15. ^ Эрдеш, Пол; Симоновиц, Миклош. «Сверхнасыщенные графы и гиперграфы» (PDF) . п. 3 . Проверено 27 ноября 2021 г.
  16. ^ Чжао , Юфэй. «Теория графов и аддитивная комбинаторика» (PDF) . стр.  16–17 . Получено 2 декабря 2019 .
  17. ^ Симоновиц, Миклош. «Экстремальные задачи на графах, вырожденные экстремальные задачи и сверхнасыщенные графы» (PDF) . стр. 17 . Получено 25 ноября 2021 г. .
  18. ^ Ковари, Т.; Т. Сос, В .; Туран, П. (1954), «К проблеме К. Заранкевича» (PDF) , Colloq. Математика. , 3 : 50–57 , doi : 10,4064/см-3-1-50-57 , MR  0065617
  19. ^ ab Simonovits, Miklós. "Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs" (PDF) . Получено 27 ноября 2021 г. .
  20. ^ Аб Эрдеш, Пол; Симоновиц, Миклош. «Результаты компактности в экстремальной теории графов» (PDF) . Проверено 27 ноября 2021 г.
  21. ^ Справочник по дискретной и комбинаторной математике Кеннет Х. Розен, Джон Г. Майклс стр. 590
  22. ^ Киваш, Питер. «Проблемы Гиперграфа Турана» (PDF) . Проверено 2 декабря 2019 г.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Forbidden_subgraph_problem&oldid=1194893475"