Задача Заранкевича

Эта статья о графах без большого полного двудольного подграфа. О числах пересечений полных двудольных графов см. «Гипотеза о числах пересечений Заранкевича» .

Проблема Заранкевича , нерешенная проблема в математике, требует максимально возможного количества ребер в двудольном графе , который имеет заданное количество вершин и не имеет полных двудольных подграфов заданного размера. Она принадлежит к области экстремальной теории графов , разделу комбинаторики , и названа в честь польского математика Казимежа Заранкевича , который предложил несколько частных случаев задачи в 1951 году.

Постановка задачи

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

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

Для $s=t=2$ эта задача такая же, как определение клеток обхватом шесть. Проблема Заранкевича, клетки и конечная геометрия тесно взаимосвязаны.

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

Примеры

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

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

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

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

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

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

Ковари, Сос и Туран первоначально доказали это неравенство для $z(n;t)$. Вскоре после этого Хильтен-Каваллиус заметил, что, по сути, тот же аргумент можно использовать для доказательства вышеуказанного неравенства. Улучшение второго члена верхней границы $z(n;t)$ дал Штефан Знам :

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

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

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

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

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

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

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

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

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

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

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

для всех постоянных значений $s,t$.

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

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

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

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

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

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

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

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

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

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

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

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

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

$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}})$

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

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

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

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

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

Нажмите ноты

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

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

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

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

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

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

Для начала позвольте $q$ быть высшей силой и $n=q^{2}$. Позволять

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

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

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

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

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

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

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

Приложения

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

См. также

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