Русская Википедия:Задача Заранкиевича

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Двудольный граф 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 эта задача совпадает с задачей определения клеток с обхватом шесть. Задача Заранкиевича, клетки и конечные геометрии сильно взаимосвязаны .

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

Примеры

Файл:Zarankiewicz-4-3.svg

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

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

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

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

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

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

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

<math>z(m,n;s,t)=O(nm^{1-1/t}+m)</math>

и

<math>z(n;t)=O(n^{2-1/t}).</math>

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

Для 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. Нижняя граница функции Заранкиевича, заданная этим семейством примеров, соответствует верхней границе, указанной И. Рейманом Шаблон:Sfn. Таким образом, для t = 2 и значений n, для которых данное построение может быть осуществлено, получаем точный ответ на задачу Заранкиевича. Для других значений n из нижних и верхних граних следует, что асимптотическиШаблон:Sfn

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

В более общем случае Шаблон:Sfn,

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

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

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

<math>z(n;t)=\Theta(n^{2-1/t})</math>

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

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

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

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

С точностью до постоянного множителя 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 в качестве подграфа, путём построения его Шаблон:Не переведено 5.

Приложения

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья. Как процитировано у Болобаша Шаблон:Harvtxt
• Шаблон:Статья
• Шаблон:Статья. Как процитировано у Болобаша Шаблон:Harvtxt
• Шаблон:Статья. Как процитировано у Болобаша Шаблон:Harvtxt
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья Эта работа основывается на более ранних границах, верных для больших значений s
  • Шаблон:Статья
• Шаблон:Книга. Репринт издания 1978 Academic Press, Шаблон:MR.
• Шаблон:Книга