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

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

Теорема Ковари–Сос–Турана, названная именами Тамаса Ковари, Веры Т.Сос и Пала Турана, даёт верхнюю границу для задачи Заранкиевича. Доказано, что если на одной из долей запрещённого двудольного графа имеется не более трёх вершин, эта граница отличается не более чем на постоянный множитель от истинного значения. Для больших запрещённых подграфов известны лучшие значения границы, и есть гипотеза, что они тесны. Приложения теоремы Ковари–Сос–Турана включают оценку числа инциденций различных типов геометрических объектов в комбинаторной геометрии.

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

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

Функция Заранкиевича z(m, n; s, t) обозначает максимальное возможное число рёбер в двудольном графе G = (U, V, E), для которого |U| = m и |V| = n, который не содержит подграфа вида Ks,t. Случай z(n, n; t, t) для краткости записывается z(n; t). Задача Заринкиевича ставит вопрос о формуле для функции Заранкиевича, или (если такую формулу установить не удастся), о тесных асимптотических границах скорости роста z(n; t) в предположении, что t фиксировано, а n стремится к бесконечности.

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

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

Примеры

Число 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 рёбрами и четырьмя вершинами в каждой доле, не содержащий K3,3 подграфа, может быть получен путём добавления длинной диагонали к графу куба. В обратном направлении, если двудольный граф с 14 рёбрами имеет по четыре вершины в каждой доле, то две вершины на каждой стороне должны иметь степень четыре. Удаление этих четырёх вершин и инцидентных им 12 рёбер оставляет непустое множество рёбер, любое из которых вместе с четырьмя удалёнными вершинами образует подграф K3,3.

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

Томаш Ковари, Вера Т.Сос и Пал Туран установили следующую верхнюю границу вскоре после постановки задачи , и эта граница получила известность как теорема Ковари – Сос – Турана:

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

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

и

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

Для t = 2 и для бесконечного числа значений n двудольный граф с n вершинами в каждой доле и Ω(n3/2) рёбрами без K2,2 может быть получен как граф Леви конечной проективной плоскости, системы по n точек и прямых, в которой каждые две точки принадлежат единственной прямой и каждые две прямые пересекаются в единственной точке. Граф, образованный из этой геометрии, имеет вершину на одной стороне для каждой точки и вершину на другой стороне для каждой прямой. Проективные плоскости, определённые над конечным полем порядка p, приводят к свободным от K2,2 графам с n = p2 + p + 1 и (p2 + p + 1)(p + 1) рёбрами. Например, граф Леви плоскости Фано даёт граф Хивуда, двудольный граф с семью вершинами в каждой доле, с 21 рёбрами и не имеющий 4-циклов, что показывает, что z(7; 2) ≥ 21. Нижняя граница функции Заранкиевича, заданная этим семейством примеров, соответствует верхней границе, указанной И. Рейманом . Таким образом, для t = 2 и значений n, для которых данное построение может быть осуществлено, получаем точный ответ на задачу Заранкиевича. Для других значений n из нижних и верхних граних следует, что асимптотически

В более общем случае ,

Для t = 3 и для бесконечного числа значений n можно построить двудольные графы с n вершинами в каждой доле и Ω(n5/3) вершинами, не имеющие подграфов K3,3, также из конечной геометрии, если в качестве вершин рассматривать точки и сферы (осторожно выбрав фиксированный радиус) в трёхмерном конечном аффинном пространстве. В этом случае рёбра представляют инциденцию точек и сфер.

Была высказана гипотеза, что

для всех постоянных значений t, но подтверждение сейчас есть только для t = 2 и t = 3 согласно вышеприведённым построениям. Тесные границы известны для пар (s, t) с большой разницей в размерах (в частности, для s ≥ (t − 1)!). Для таких пар

что делает вышеупомянутую гипотезу правдоподобной. .

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

С точностью до постоянного множителя z(n; t) ограничивает также число рёбер графа с n вершинами (не обязательно двудольного), который не содержит Kt,t в качестве подграфа. В одну сторону, двудольный граф с z(n; t) рёбрами и n вершинами в каждой доле можно уменьшить до графа с n вершинами и z(n; t)/4 рёбрами путём выбора n/2 вершин случайным образом из общего числа вершин графа. В обратном направлении граф с n вершинами без подграфов Kt,t можно преобразовать в двудольный граф с n вершинами в каждой доле и удвоенным числом рёбер, который по-прежнему не будет содержать Kt,t в качестве подграфа, путём построения его двудольного двойного накрытия.

Приложения

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