проблема Заранкевича

Задача Заранкевича — нерешённая задача в математике, требующая нахождения наибольшего возможного числа рёбер в двудольном графе , имеющем заданное число вершин и не имеющем полных двудольных подграфов заданного размера. ^[1] Она относится к области экстремальной теории графов , разделу комбинаторики , и названа в честь польского математика Казимежа Заранкевича , который предложил несколько частных случаев задачи в 1951 году. ^[2]

Постановка проблемы

Двудольный граф состоит из двух непересекающихся множеств вершин и , и множества ребер, каждое из которых соединяет вершину из с вершиной из . Никакие два ребра не могут соединять одну и ту же пару вершин. Полный двудольный граф — это двудольный граф, в котором каждая пара вершины из и вершины из соединена друг с другом. Полный двудольный граф, в котором имеет вершины и имеет вершины, обозначается . Если — двудольный граф и существует множество вершин из и вершин из , которые все соединены друг с другом, то эти вершины индуцируют подграф вида . (В этой формулировке порядок и имеет значение: множество вершин должно быть из , а множество вершин должно быть из , а не наоборот.) ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle s}$ ${\displaystyle V}$ ${\displaystyle t}$ ${\displaystyle K_{s,t}}$ ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle s}$ ${\displaystyle U}$ ${\displaystyle t}$ ${\displaystyle V}$ ${\displaystyle K_{s,t}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle U}$ ${\displaystyle t}$ ${\displaystyle V}$

Функция Заранкевича обозначает максимально возможное число ребер в двудольном графе , для которого и , но который не содержит подграфа вида . В качестве сокращения для важного специального случая, совпадает с . Задача Заранкевича требует формулы для функции Заранкевича или (если это невозможно) для точных асимптотических оценок скорости роста, предполагая, что является фиксированной константой, в пределе, когда стремится к бесконечности. ${\displaystyle z(m,n;s,t)}$ ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle |U|=m}$ ${\displaystyle |V|=n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle z(n;t)}$ ${\displaystyle z(n,n;t,t)}$ ${\displaystyle z(n;t)}$ ${\displaystyle t}$ ${\displaystyle n}$

Для этой задачи то же самое, что и для определения клеток с обхватом шесть. Задача Заранкевича, клетки и конечная геометрия тесно взаимосвязаны. ^[3] ${\displaystyle s=t=2}$

Эту же задачу можно сформулировать в терминах цифровой геометрии . Возможные ребра двудольного графа можно визуализировать как точки прямоугольника в целочисленной решетке , а полный подграф — это набор строк и столбцов в этом прямоугольнике, в котором присутствуют все точки. Таким образом, обозначает максимальное количество точек, которые можно разместить в сетке таким образом, что никакое подмножество строк и столбцов не образует полную сетку. ^[4] Альтернативное и эквивалентное определение заключается в том, что — это наименьшее целое число , такое что каждая (0,1)-матрица размера с единицами должна иметь набор строк и столбцов, такой что соответствующая подматрица состоит только из единиц . ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle |U|\times |V|}$ ${\displaystyle z(m,n;s,t)}$ ${\displaystyle m\times n}$ ${\displaystyle s\times t}$ ${\displaystyle z(m,n;s,t)}$ ${\displaystyle k}$ ${\displaystyle m\times n}$ ${\displaystyle k+1}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s\times t}$

Примеры

Двудольный граф с 4 вершинами на каждой стороне, 13 ребрами и без подграфа, а также эквивалентный набор из 13 точек в сетке 4 × 4, показывающий, что . ${\displaystyle K_{3,3}}$ ${\displaystyle z(4;3)\geq 13}$

Число запрашивает максимальное количество ребер в двудольном графе с вершинами на каждой стороне, который не имеет 4-цикла (его обхват равен шести или более). Таким образом, (достигается путем из трех ребер), и ( шестиугольник ). ${\displaystyle z(n;2)}$ ${\displaystyle n}$ ${\displaystyle z(2;2)=3}$ ${\displaystyle z(3;2)=6}$

В своей первоначальной формулировке задачи Заранкевич просил значения для . Ответы вскоре были предоставлены Вацлавом Серпинским : , , и . ^[4] Случай относительно прост: двудольный граф с 13 ребрами и четырьмя вершинами на каждой стороне двудольного графа, не имеющий подграфа, может быть получен путем добавления одной из длинных диагоналей к графу куба . В другом направлении, если двудольный граф с 14 ребрами имеет четыре вершины на каждой стороне, то две вершины на каждой стороне должны иметь степень четыре. Удаление этих четырех вершин и их 12 инцидентных ребер оставляет непустое множество ребер, любое из которых вместе с четырьмя удаленными вершинами образует подграф. ${\displaystyle z(n;3)}$ ${\displaystyle n=4,5,6}$ ${\displaystyle z(4;3)=13}$ ${\displaystyle z(5;3)=20}$ ${\displaystyle z(6;3)=26}$ ${\displaystyle z(4;3)}$ ${\displaystyle K_{3,3}}$ ${\displaystyle K_{3,3}}$

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

Теорема Кёвари–Соша–Турана дает верхнюю оценку решения проблемы Заранкевича. Его основали Тамаш Ковари, Вера Т. Сос и Пал Туран вскоре после того, как проблема была поставлена:

${\displaystyle z(m,n;s,t)<(s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m.}$

Ковари, Шош и Туран первоначально доказали это неравенство для . ^[5] Вскоре после этого Хильтен-Каваллиус заметил, что по сути тот же аргумент может быть использован для доказательства вышеуказанного неравенства. ^[6] Улучшение второго члена верхней границы было дано Штефаном Знамом : ^[7] ${\displaystyle z(n;t)}$ ${\displaystyle z(n;t)}$

${\displaystyle z(n;t)<(t-1)^{1/t}n^{2-1/t}+{\frac {1}{2}}(t-1)n+1.}$

Если и предполагаются постоянными, то асимптотически, используя обозначение О большое , эти формулы можно выразить как ${\displaystyle s}$ ${\displaystyle t}$

${\displaystyle z(m,n;s,t)=O(mn^{1-1/s}+n)}$;

${\displaystyle z(m,n;s,t)=O(nm^{1-1/t}+m)}$.

В частном случае , предполагая без потери общности, что , имеем асимптотическую верхнюю границу ${\displaystyle m=n}$ ${\displaystyle s\leq t}$

${\displaystyle z(n,n;s,t)=O(n^{2-1/s}).}$

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

Можно проверить, что среди двух асимптотических верхних границ в предыдущем разделе первая граница лучше, когда , а вторая граница становится лучше, когда . Таким образом, если можно показать нижнюю границу для , которая совпадает с верхней границей с точностью до константы, то с помощью простого аргумента выборки (либо на двудольном графе, либо на двудольном графе, который достигает максимального числа ребер) мы можем показать, что для всех одна из двух верхних границ выше точна с точностью до константы. Это приводит к следующему вопросу: верно ли, что для любых фиксированных и мы имеем ${\displaystyle z(m,n;s,t)}$ ${\displaystyle m=o(n^{s/t})}$ ${\displaystyle m=\omega (n^{s/t})}$ ${\displaystyle z(n^{s/t},n;s,t)}$ ${\displaystyle n^{t/s}\times t}$ ${\displaystyle m\times m^{s/t}}$ ${\displaystyle m,n}$ ${\displaystyle s\leq t}$ ${\displaystyle m\leq n^{s/t}}$

${\displaystyle z(m,n;s,t)=\Omega (mn^{1-1/s})}$? ^[8]

В частном случае , с точностью до постоянных множителей, имеет тот же порядок, что и , максимальное число ребер в -вершинном (не обязательно двудольном) графе, который не имеет в качестве подграфа. В одном направлении двудольный граф с вершинами на каждой стороне и ребрами должен иметь подграф с вершинами и по крайней мере ребрами; это можно увидеть, выбрав вершины равномерно случайным образом с каждой стороны и взяв математическое ожидание. В другом направлении мы можем преобразовать граф с вершинами и без копии в двудольный граф с вершинами на каждой стороне его двудольного графа, вдвое большим количеством ребер и по-прежнему без копии , взяв его двудольное двойное покрытие . ^[9] То же, что и выше, с соглашением, что , было высказано предположение, что ${\displaystyle m=n}$ ${\displaystyle z(n,n;s,t)}$ ${\displaystyle {\text{ex}}(n,K_{s,t})}$ ${\displaystyle n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle n}$ ${\displaystyle z(n,n;s,t)}$ ${\displaystyle n}$ ${\displaystyle z(n,n;s,t)/4}$ ${\displaystyle n/2}$ ${\displaystyle n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle s\leq t}$

${\displaystyle z(n,n;s,t)=\Theta (n^{2-1/s})}$

для всех постоянных значений . ^[10] ${\displaystyle s,t}$

Для некоторых конкретных значений (например, для достаточно больших, чем , или для ) приведенные выше утверждения были доказаны с использованием различных алгебраических и случайных алгебраических конструкций. В то же время ответ на общий вопрос нам пока неизвестен. ${\displaystyle s,t}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s=2}$

Графы инцидентности в конечной геометрии

Граф Леви плоскости Фано порождает граф Хивуда — двудольный граф с семью вершинами на каждой стороне, 21 ребром и без 4-циклов.

Для двудольный граф с вершинами на каждой стороне, ребрами и без может быть получен как граф Леви или граф инцидентности точка-прямая проективной плоскости порядка , система точек и прямых, в которой каждые две точки определяют уникальную прямую, и каждые две прямые пересекаются в уникальной точке. Мы строим двудольный граф, связанный с этой проективной плоскостью, которая имеет одну вершинную часть в качестве своих точек, другую вершинную часть в качестве своих прямых, так что точка и прямая связаны тогда и только тогда, когда они инцидентны в проективной плоскости. Это приводит к -свободному графу с вершинами и ребрами. Поскольку эта нижняя граница совпадает с верхней границей, данной И. Рейманом, ^[11], мы имеем асимптотику ^[12] ${\displaystyle s=t=2}$ ${\displaystyle n}$ ${\displaystyle \Omega (n^{3/2})}$ ${\displaystyle K_{2,2}}$ ${\displaystyle q}$ ${\displaystyle q^{2}+q+1}$ ${\displaystyle q^{2}+q+1}$ ${\displaystyle K_{2,2}}$ ${\displaystyle q^{2}+q+1}$ ${\displaystyle (q^{2}+q+1)(q+1)}$

${\displaystyle z(n;2)=(1/2+o(1))n^{3/2}.}$

Для двудольные графы с вершинами на каждой стороне, ребрами и без них снова могут быть построены из конечной геометрии, если позволить вершинам представлять точки и сферы (тщательно выбранного фиксированного радиуса) в трехмерном конечном аффинном пространстве, а ребрам — инцидентности точка-сфера. ^[13] ${\displaystyle s=t=3}$ ${\displaystyle n}$ ${\displaystyle \Omega (n^{5/3})}$ ${\displaystyle K_{3,3}}$

В более общем случае рассмотрим и любой . Пусть будет -элементным конечным полем, а будет элементом мультипликативного порядка , в том смысле, что образуют -элементную подгруппу мультипликативной группы . Мы говорим, что два ненулевых элемента эквивалентны, если у нас есть и для некоторого . Рассмотрим граф на множестве всех классов эквивалентности , такой что и связаны тогда и только тогда, когда . Можно проверить, что является корректно определенным и свободным от , и каждая вершина в имеет степень или . Следовательно, мы имеем верхнюю границу ^[14] ${\displaystyle s=2}$ ${\displaystyle t}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$ ${\displaystyle h}$ ${\displaystyle t}$ ${\displaystyle H=\{1,h,\dots ,h^{t-1}\}}$ ${\displaystyle t}$ ${\displaystyle \mathbb {F} _{q}^{*}}$ ${\displaystyle (a,b),(a',b')\in \mathbb {F} _{q}\times \mathbb {F} _{q}}$ ${\displaystyle a'=h^{d}a}$ ${\displaystyle b'=h^{d}b}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle \langle a,b\rangle }$ ${\displaystyle \langle a,b\rangle }$ ${\displaystyle \langle x,y\rangle }$ ${\displaystyle ax+by\in H}$ ${\displaystyle G}$ ${\displaystyle K_{2,t+1}}$ ${\displaystyle G}$ ${\displaystyle q}$ ${\displaystyle q-1}$

${\displaystyle z(n,n;2,t+1)=(t^{1/2}+o(1))n^{3/2}.}$

Нормированные графы и проективные нормированные графы

Для достаточно больших, чем , вышеуказанная гипотеза была проверена Колларом, Роньяи и Сабо ^[15] и Алоном, Роньяи и Сабо ^[16] с использованием построения норменных графов и проективных норменных графов над конечными полями. ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle z(n,n;s,t)=\Theta (n^{2-1/s})}$

Для рассмотрим норменный граф NormGraph _p,s с множеством вершин , такой, что каждые две вершины связаны тогда и только тогда , когда , где — норменная карта ${\displaystyle t>s!}$ ${\displaystyle \mathbb {F} _{p^{s}}}$ ${\displaystyle a,b\in \mathbb {F} _{p^{s}}}$ ${\displaystyle N(a+b)=1}$ ${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$

${\displaystyle N(x)=x\cdot x^{p}\cdot x^{p^{2}}\cdots x^{p^{s-1}}=x^{(p^{s}-1)/(p-1)}.}$

Нетрудно проверить, что граф имеет вершины и по крайней мере ребра. Чтобы увидеть, что этот граф -свободен , заметьте, что любой общий сосед вершин должен удовлетворять ${\displaystyle p^{s}}$ ${\displaystyle p^{2s-1}/2}$ ${\displaystyle K_{s,s!+1}}$ ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle y_{1},\ldots ,y_{s}\in \mathbb {F} _{p^{s}}}$

${\displaystyle 1=N(x+y_{i})=(x+y_{i})\cdot (x+y_{i})^{p}\cdots (x+y_{i})^{p^{s-1}}=(x+y_{i})\cdot (x^{p}+y_{i}^{p})\cdots (x^{p^{s-1}}+y_{i}^{p^{s-1}})}$

для всех , что является системой уравнений, имеющей не более решений. ${\displaystyle i=1,\ldots ,s}$ ${\displaystyle s!}$

Тот же результат можно доказать для всех с помощью проективного норменного графа , конструкции немного более сильной, чем вышеприведенная. Проективный норменный граф ProjNormGraph _p,s — это граф на множестве вершин , такой, что две вершины смежны тогда и только тогда, когда , где — норменное отображение, определенное как . Аналогичным рассуждением, приведенным выше, можно проверить, что это -свободный граф с ребрами. ${\displaystyle t>(s-1)!}$ ${\displaystyle \mathbb {F} _{p^{s-1}}\times \mathbb {F} _{p}^{\times }}$ ${\displaystyle (X,x),(Y,y)}$ ${\displaystyle N(X+Y)=xy}$ ${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$ ${\displaystyle N(x)=x^{(p^{s}-1)/(p-1)}}$ ${\displaystyle K_{s,t}}$ ${\displaystyle \Omega (n^{2-1/s})}$

Подход с использованием графика нормы выше также дает точные нижние границы для определенных выборов . ^[16] В частности, для , , и мы имеем ${\displaystyle z(m,n;s,t)}$ ${\displaystyle m,n}$ ${\displaystyle s\geq 2}$ ${\displaystyle t>s!}$ ${\displaystyle n^{1/t}\leq m\leq n^{1+1/t}}$

${\displaystyle z(m,n;s,t)=\Theta (mn^{1-1/s}).}$

В случае рассмотрим двудольный граф с двудольностью , такой что и . Для и пусть в тогда и только тогда, когда , где — норменное отображение, определенное выше. Чтобы увидеть, что является -свободным, рассмотрим кортежи . Заметим, что если кортежи имеют общего соседа, то должны быть различными. Используя ту же верхнюю границу числа решений системы уравнений, мы знаем, что эти кортежи имеют не более общих соседей. ${\displaystyle m=(1+o(1))n^{1+1/s}}$ ${\displaystyle G}$ ${\displaystyle V=V_{1}\cup V_{2}}$ ${\displaystyle V_{1}=\mathbb {F} _{p^{t}}\times \mathbb {F} _{p}^{\times }}$ ${\displaystyle V_{2}=\mathbb {F} _{p^{t}}}$ ${\displaystyle A\in V_{1}}$ ${\displaystyle (B,b)\in V_{2}}$ ${\displaystyle A\sim (B,b)}$ ${\displaystyle G}$ ${\displaystyle N(A+B)=b}$ ${\displaystyle N(\cdot )}$ ${\displaystyle G}$ ${\displaystyle K_{s,t}}$ ${\displaystyle s}$ ${\displaystyle (B_{1},b_{1}),\ldots ,(B_{s},b_{s})\in V_{1}}$ ${\displaystyle s}$ ${\displaystyle B_{i}}$ ${\displaystyle s}$ ${\displaystyle s!<t}$

Разделы клики

Используя связанный результат о числах разбиения клик, Алон, Меллингер, Мубаи и Верстраэте ^[17] доказали точную нижнюю границу для произвольного : если , то мы имеем ${\displaystyle z(m,n;2,t)}$ ${\displaystyle t}$ ${\displaystyle m=(1+o(1))n^{t/2}}$

${\displaystyle z(m,n;2,t)=(1+o(1))mn^{1/2}}$.

Для мы говорим, что набор подмножеств является кликовым разбиением , если образуют разбиение . Заметим, что для любого , если существует некоторое из размера и , такое, что существует разбиение на клики размера , то мы имеем . Действительно, предположив, что является разбиением на клики размера , мы можем позволить быть двудольным графом с и , таким, что в тогда и только тогда, когда . Поскольку образуют кликовое разбиение, не может содержать копию . ${\displaystyle 2\leq t\leq n}$ ${\displaystyle A_{1},\dots ,A_{\ell }\subset [n]}$ ${\displaystyle H\subset {[n] \choose t}}$ ${\displaystyle \bigcup _{i=1}^{\ell }{A_{i} \choose t}}$ ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle H\subset {[n] \choose t}}$ ${\displaystyle (1-o(1)){n \choose t}}$ ${\displaystyle m=(1+o(1)){n \choose t}/{k \choose t}}$ ${\displaystyle H}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle z(m,n;2,t)=km}$ ${\displaystyle A_{1},\dots ,A_{m}\subset [n]}$ ${\displaystyle H}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle m\times n}$ ${\displaystyle V_{1}=\{A_{1},\dots ,A_{m}\}}$ ${\displaystyle V_{2}=[n]}$ ${\displaystyle A_{i}\sim v}$ ${\displaystyle G}$ ${\displaystyle v\in A_{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle G}$ ${\displaystyle K_{2,t}}$

Осталось показать, что такое разбиение клик существует для любого . Чтобы показать это, пусть будет конечным полем размера и . Для каждого многочлена степени не выше , определим . Пусть будет совокупностью всех , так что и каждый имеет размер . Очевидно, что никакие два члена из не могут иметь общих членов. Поскольку единственные -множества из , которые не принадлежат , - это те, которые имеют по крайней мере две точки, разделяющие одну и ту же первую координату, мы знаем, что почти все -подмножества из содержатся в некоторых . ${\displaystyle m=(1+o(1))n^{t/2}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$ ${\displaystyle V=\mathbb {F} _{q}\times \mathbb {F} _{q}}$ ${\displaystyle p(\cdot )}$ ${\displaystyle t-1}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle C_{p}=\{(x,p(x)):x\in \mathbb {F} _{q}\}\subset V}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C_{p}}$ ${\displaystyle |{\mathcal {C}}|=q^{t}=n^{t/2}}$ ${\displaystyle C_{p}}$ ${\displaystyle q={\sqrt {n}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle V}$ ${\displaystyle H}$ ${\displaystyle t}$ ${\displaystyle V}$ ${\displaystyle C_{p}}$

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

Альтернативные доказательства для достаточно больших, чем были также даны Благоевичем, Бухом и Карасевым ^[18] и Бухом ^[19] с использованием метода случайных алгебраических конструкций. Основная идея состоит в том, чтобы взять случайный многочлен и рассмотреть граф между двумя копиями, ребрами которого являются все те пары, такие, что . ${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle f:\mathbb {F} _{q}^{s}\times \mathbb {F} _{q}^{s}\rightarrow \mathbb {F} _{q}}$ ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle (x,y)}$ ${\displaystyle f(x,y)=0}$

Для начала пусть будет степенью простого числа и . Пусть ${\displaystyle q}$ ${\displaystyle n=q^{2}}$

${\displaystyle f\in \mathbb {F} _{q}[x_{1},\dots ,x_{s},y_{1},\dots ,t_{s}]_{\leq s^{2}}}$

будет случайным многочленом со степенью не более , степенью не более , и, кроме того, удовлетворяющим для всех . Пусть будет ассоциированным случайным графом на множестве вершин , таким, что две вершины и являются смежными тогда и только тогда, когда . ${\displaystyle s^{2}}$ ${\displaystyle X=(x_{1},\dots ,x_{s})}$ ${\displaystyle s^{2}}$ ${\displaystyle Y=(y_{1},\dots ,y_{s})}$ ${\displaystyle f(X,Y)=f(Y,X)}$ ${\displaystyle X,Y}$ ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f(x,y)=0}$

Для доказательства асимптотической нижней границы достаточно показать, что ожидаемое число ребер в равно . Для каждого -подмножества обозначим через подмножество вершин , которое «исчезает на »: ${\displaystyle G}$ ${\displaystyle \Omega (q^{2s-1})}$ ${\displaystyle s}$ ${\displaystyle U\subset \mathbb {F} _{q}^{s}}$ ${\displaystyle Z_{U}}$ ${\displaystyle \mathbb {F} _{q}^{s}\setminus U}$ ${\displaystyle f(\cdot ,U)}$

${\displaystyle Z_{U}=\{x\in \mathbb {F} _{q}^{s}\setminus U:f(x,u)=0{\text{ for all }}u\in U\}}$.

Используя границу Ланга-Вейля для полиномов по , мы можем вывести, что всегда выполняется или для некоторой большой константы , что подразумевает ${\displaystyle f(\cdot ,u)}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle Z_{U}\leq C}$ ${\displaystyle Z_{U}>q/2}$ ${\displaystyle C}$

${\displaystyle \mathbb {P} (|Z_{U}|>C)=\mathbb {P} (|Z_{U}|>q/2)}$.

Так как выбирается случайным образом над , нетрудно показать, что вероятность правой стороны мала, поэтому ожидаемое число -подмножеств с также оказалось малым. Если мы удалим вершину из каждого такого , то полученный граф будет свободным, а ожидаемое число оставшихся ребер все еще велико. Это завершает доказательство того, что для всех достаточно больших относительно . Совсем недавно был получен ряд результатов, подтверждающих гипотезу для различных значений , используя похожие идеи, но с большим количеством инструментов из алгебраической геометрии. ^{[8] [20]} ${\displaystyle f}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle s}$ ${\displaystyle U}$ ${\displaystyle |Z_{U}|>C}$ ${\displaystyle U}$ ${\displaystyle K_{s,C+1}}$ ${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle z(m,n;s,t)=\Omega (n^{2-1/s})}$ ${\displaystyle s,t}$

Приложения

Теорема Ковари–Шоша–Турана использовалась в дискретной геометрии для ограничения числа инцидентностей между геометрическими объектами различных типов. В качестве простого примера, множество точек и прямых на евклидовой плоскости обязательно не имеет , поэтому по теореме Ковари–Шоша–Турана оно имеет инцидентности точек и прямых. Эта граница точна, когда намного больше , но не когда и почти равны, в этом случае теорема Семереди–Троттера обеспечивает более точную границу. Однако теорему Семереди–Троттера можно доказать, разделив точки и прямые на подмножества, для которых граница Ковари–Шоша–Турана точна. ^[21] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle K_{2,2}}$ ${\displaystyle O(nm^{1/2}+m)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(n^{2/3}m^{2/3}+n+m)}$

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

• Граф без биклики , разреженный граф, разреженность которого контролируется решением задачи Заранкевича
• Проблема запрещенного подграфа , недвудольное обобщение проблемы Заранкевича
• Характеристика запрещенных графов , семейства графов, определяемые запрещенными подграфами различных типов
• Теорема Турана , ограничение на число ребер графа с запрещенным полным подграфом

Ссылки

1. Боллобас, Бела (2004), "VI.2 Полные подграфы r -дольных графов", Extremal Graph Theory , Минеола, Нью-Йорк: Dover Publications Inc., стр. 309–326, MR  2078877. Перепечатка издания Academic Press 1978 года, MR 0506522.
2. Заранкевич, К. (1951), «Проблема P 101», Colloq. Математика. , 2 : 301. Как цитирует Боллобаш (2004).
3. "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2016-03-04 . Получено 2014-09-16 .{{cite web}}: CS1 maint: archived copy as title (link)
4. Серпински, В. (1951), «Сур ип проблема, касающаяся результата в 36 баллов», Ann. Соц. Полон. Математика. , 24 : 173–174, МР  0059876.
5. Ковари, Т.; Т. Сос, В .; Туран, П. (1954), «К проблеме К. Заранкевича» (PDF) , Коллоквиум Math. , 3 : 50–57, doi : 10,4064/см-3-1-50-57 , MR  0065617.
6. Хильтен-Каваллиус, К. (1958), «Об одной комбинаторной проблеме», Colloquium Mathematicum , 6 : 59–65, doi : 10.4064/cm-6-1-61-65 , MR  0103158. Как цитирует Боллобаш (2004).
7. Знам, Ш. (1963), «Об одной комбинаторной задаче К. Заранкевича», Colloquium Mathematicum , 11 : 81–84, doi : 10.4064/cm-11-1-81-84 , MR  0162733. Как цитирует Боллобаш (2004).
8. Conlon, David (2021), «Некоторые замечания по проблеме Заранкевича», Математические труды Кембриджского философского общества , 173 : 155–161, arXiv : 2007.12816 , doi : 10.1017/S0305004121000475, S2CID  220793154.
9. Боллобаш (2004), Теорема 2.3, стр. 310.
10. Боллобас (2004), Гипотеза 15, стр. 312.
11. Рейман, И. (1958), «Über ein Проблема фон К. Заранкевича», Acta Mathematica Academiae Scientiarum Hungaricae , 9 (3–4): 269–273, doi : 10.1007/bf02020254, MR  0101250, S2CID  121692172.
12. Боллобас (2004), Следствие 2.7, с. 313.
13. Браун, WG (1966), «О графах, не содержащих граф Томсена», Канадский математический бюллетень , 9 (3): 281–285, doi : 10.4153/CMB-1966-036-2 , MR  0200182, S2CID  121306253.
14. Фюреди, Золтан (1996), «Новая асимптотика для двудольных чисел Турана», Журнал комбинаторной теории , серия A, 75 (1): 141–144, doi : 10.1006/jcta.1996.0067 , MR  1395763.
15. Коллар, Янош; Роньяи, Лайош; Сабо, Тибор (1996), «Графы норм и двудольные числа Турана», Combinatorica , 16 (3): 399–406, doi : 10.1007/BF01261323, MR  1417348, S2CID  26363618.
16. Alon, Noga ; Rónyai, Lajos; Szabó, Tibor (1999), "Норм-графы: вариации и приложения", Журнал комбинаторной теории , Серия B, 76 (2): 280–290, doi : 10.1006/jctb.1999.1906 , MR  1699238.
17. Алон, Нога ; Меллингер, Кейт Э.; Мубайи, Дхрув; Верстраете, Жак (2012), «Теорема де Брейна-Эрдёша для гиперграфов», Des. Коды Криптогр. , 65 (3): 233–245, arXiv : 1007.4150 , doi : 10.1007/s10623-011-9555-4, S2CID  15064936.
18. Благоевич, Павле; Бух, Борис; Карасев, Роман (2013), «Числа Турана для графов, свободных от K _s,t : топологические препятствия и алгебраические конструкции», Israel Journal of Mathematics , 197 : 199–214, arXiv : 1108.5254 , doi : 10.1007/s11856-012-0184-z.
19. Бух, Борис (2015), "Случайное алгебраическое построение экстремальных графов", Bull. London Math. Soc. , 47 : 939–945, arXiv : 1409.3856.
20. Бух, Борис (2021), Экстремальные графы без экспоненциально малых биклик , arXiv : 2107.04167.
21. Матоушек, Йиржи (2002), Лекции по дискретной геометрии , Graduate Texts in Mathematics, т. 212, Нью-Йорк: Springer-Verlag, стр. 65–68, doi :10.1007/978-1-4613-0039-7, ISBN 0-387-95373-6, г-н  1899299.