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

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

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

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

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

Двудольный граф с 4 вершинами в обоих долях и 13 рёбрами, не содержащий подграфа K_3,3. Справа — эквивалентное множество из 13 точек на решётке, a 4 × 4, из которого видно, что z(4; 3) ≥ 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 [4]. Случай z(4; 3) относительно прост — двудольный граф с 13 рёбрами и четырьмя вершинами в каждой доле, не содержащий K_3,3 подграфа, может быть получен путём добавления длинной диагонали к графу куба. В обратном направлении, если двудольный граф с 14 рёбрами имеет по четыре вершины в каждой доле, то две вершины на каждой стороне должны иметь степень четыре. Удаление этих четырёх вершин и инцидентных им 12 рёбер оставляет непустое множество рёбер, любое из которых вместе с четырьмя удалёнными вершинами образует подграф K_3,3.

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• W. Sierpiński. Sur un problème concernant un reseau à 36 points // Ann. Soc. Polon. Math.. — 1951. — Т. 24. — С. 173–174.
• K. Zarankiewicz. Problem P 101 // Colloq. Math.. — 1951. — Т. 2. — С. 301.. Как процитировано у Болобаша Bollobás (2004)
• T. Kővári, Vera T. Sós, P. Turán. On a problem of K. Zarankiewicz // Colloquium Math.. — 1954. — Т. 3. — С. 50–57.
• I. Reiman. Über ein Problem von K. Zarankiewicz // Acta Mathematica Academiae Scientiarum Hungaricae. — 1958. — Т. 9. — С. 269–273. — doi:10.1007/bf02020254.. Как процитировано у Болобаша Bollobás (2004)
• C. Hyltén-Cavallius. On a combinatorical problem // Colloquium Mathematicum. — 1958. — Т. 6. — С. 59–65.. Как процитировано у Болобаша Bollobás (2004)
• Š. Štefan Znám. On a combinatorical problem of K. Zarankiewicz // Colloquium Mathematicum. — 1963. — Т. 11. — С. 81–84.
• W. G. Brown. On graphs that do not contain a Thomsen graph // Canadian Mathematical Bulletin. — 1966. — Т. 9. — С. 281–285. — doi:10.4153/CMB-1966-036-2.
• Zoltán Füredi. New asymptotics for bipartite Turán numbers // Journal of Combinatorial Theory. — 1996. — Т. 75, вып. 1. — С. 141–144. — doi:10.1006/jcta.1996.0067.
• Noga Alon, Lajos Rónyai, Tibor Szabó. Norm-graphs: variations and applications // Journal of Combinatorial Theory. — 1999. — Т. 76, вып. 2. — С. 280–290. — doi:10.1006/jctb.1999.1906. Эта работа основывается на более ранних границах, верных для больших значений s
  • János Kollár, Lajos Rónyai, Tibor Szabó. Norm-graphs and bipartite Turán numbers // Combinatorica. — 1996. — Т. 16, вып. 3. — С. 399–406. — doi:10.1007/BF01261323.
• Béla Bollobás. Extremal Graph Theory. — Mineola, NY: Dover Publications Inc., 2004. — С. 309–326.. Репринт издания 1978 Academic Press, MR: 0506522.
• Jiří Matoušek. Lectures on discrete geometry. — New York: Springer-Verlag, 2002. — Т. 212. — С. 65–68. — (Graduate Texts in Mathematics). — ISBN 0-387-95373-6. — doi:10.1007/978-1-4613-0039-7.