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

Зада́ча Заранке́вича — відкрита проблема в математиці, ставить питання про найбільшу можливу кількість ребер у двочастковому графі, який має задану кількість вершин, але не містить повних двочасткових підграфів заданого розміруШаблон:Sfn. Задача належить до галузі екстремальної теорії графів, гілки комбінаторики, і названа ім'ям польського математика Шаблон:Не перекладено, який описав деякі часткові випадки цієї задачі 1951 рокуШаблон:Sfn.

Теорема Коварі — Шош — Турана, названа іменами Тамаса Коварі, Віри Шош і Пала Турана, дає верхню межу для задачі Заранкевича. Доведено, що якщо на одній із часток забороненого двочасткового графа є не більше трьох вершин, ця межа відрізняється не більше ніж на сталий множник від істинного значення. Для великих заборонених підграфів відомі найкращі значення межі, і є гіпотеза, що вони тісні. Застосування теореми Коварі — Шош — Турана включають оцінення числа інциденцій різних типів геометричних об'єктів у комбінаторній геометрії.

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

Двочастковий граф $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$ ця задача збігається із задачею визначення кліток із обхватом шість. Задача Заранкевича, клітки та скінченні геометрії сильно взаємопов'язані.

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

Приклади

Двочастковий граф із 4 вершинами в обох частках і 13 ребрами, що не містить підграфа $K_{3,3}$. Праворуч — еквівалентна множина з 13 точок на ґратці 4 × 4, з якої видно, що $z(4;3)\ge 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}$.

Верхні межі

Томаш Коварі, Віра Шош і Пал Туран, невдовзі після постановки задачі, встановили таку верхню межуШаблон:Sfn, відому як теорема Коварі — Шош — Турана:

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

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

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

Якщо зафіксувати $s$ і $t$, використовуючи нотацію «O» велике, можна в асимптотиці ці формули переписати так:

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

і

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

Нижні межі

Для $t=2$ і для нескінченного числа значень $n$ двочастковий граф з $n$ вершинами в кожній частці і $\mathrm{\Omega }(n^{3/2})$ ребрами без $K_{2,2}$ можна отримати як граф Леві скінченної проєктивної площини системи по $n$ точок і прямих, у якій кожні дві точки належать єдиній прямій і кожні дві прямі перетинаються в єдиній точці. Граф, утворений із цієї геометрії, має вершину з одного боку для кожної точки і вершину з іншого боку для кожної прямої. Проєктивні площини, визначені над скінченним полем порядку p приводять до вільних від $K_{2,2}$ графів з $n=p^2+p+1$ і $(p^2+p+1)(p+1)$ ребрами. Наприклад, граф Леві площині Фано дає граф Хівуда, двочастковий граф зі сімома вершинами в кожній частці, з 21 ребром і без 4-циклів, що показує, що $z(7;2)\ge 21$. Нижня межа функції Заранкевича, задана цим сімейством прикладів, відповідає верхній межі, яку вказав І. РейманШаблон:Sfn. Отже, для $t=2$ та значень $n$, для яких цю побудову можна здійснити, отримуємо точну відповідь на задачу Заранкевича. Для інших значень $n$ із нижніх і верхніх меж випливає, що асимптотичноШаблон:Sfn

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

У загальнішому випадкуШаблон:Sfn,

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

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

Висловлено гіпотезу, що

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

для всіх сталих значень $t$, але підтвердження зараз є тільки для $t=2$ і $t=3$ за наведеними вище побудовамиШаблон:Sfn. Тісні межі відомі для пар $(s,t)$ з великою різницею розмірів (зокрема, для $s\ge (t-1)!$). Для таких пар

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

що робить згадану вище гіпотезу правдоподібноюШаблон: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}$ як підграф, побудувавши його Шаблон:Не перекладено.

Застосування

Теорему Коварі — Шош — Турана використовують у комбінаторній геометрії для обмеження кількості інциденцій між геометричними об'єктами різних типів. Наприклад, множина $n$ точок і $m$ прямих на евклідовій площині не містить $K_{2,2}$, так що за теоремою Коварі — Шош — Турана ця конфігурація має не більше $O(n{m}^{1/2}+m)$ інциденцій точка-пряма. Ця межа близька, якщо m набагато більше від n, але при майже однакових m і n теорема Семереді — Троттера дає тіснішу межу $O(n^{2/3}{m}^{2/3}+n+m)$. Проте теорему Семереді — Троттера можна довести, поділивши точки й прямі на підмножини, для яких межі Коварі — Шош — Турана тісніШаблон:Sfn.

Див. також

• Вільні від біклік графи — розріджені графи, розрідженість яких керується розв'язанням задачі Заранкевича
• Шаблон:Не перекладено — узагальнення задачі Заранкевича на недвочасткові графи
• Характеризація забороненими графами, сімейства графів, визначені забороною підграфів певного виду
• Теорема Турана — межа числа ребер графа із забороненими повними підграфами

Література

• Шаблон:Стаття
• Шаблон:Стаття Як процитовано в Болобаша Шаблон:Harvtxt
• Шаблон:Стаття
• Шаблон:Стаття. Как процитировано у Болобаша Шаблон:Harvtxt
• Шаблон:Стаття Як процитовано в Болобаша Шаблон:Harvtxt
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття Ця праця ґрунтується на раніших межах, істинних для більших значень s
  • Шаблон:Стаття
• Шаблон:Книга. Репринт видання 1978 Academic Press, Шаблон:MathSciNet.
• Шаблон:Книга