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

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

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

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

Двочастковий граф $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$. Альтернативне та еквівалентне визначення, що $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)\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.$

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

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

і

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

Нижні межі

Для $t=2$ і для нескінченного числа значень $n$ двочастковий граф з $n$ вершинами в кожній частці і $\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)\geq 21$. Нижня межа функції Заранкевича, задана цим сімейством прикладів, відповідає верхній межі, яку вказав І. Рейман. Отже, для $t=2$ та значень $n$, для яких цю побудову можна здійснити, отримуємо точну відповідь на задачу Заранкевича. Для інших значень $n$ із нижніх і верхніх меж випливає, що асимптотично

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

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

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

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

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

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

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

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

що робить згадану вище гіпотезу правдоподібною.

Недвочасткові графи

З точністю до сталого множника $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(nm^{1/2}+m)$ інциденцій точка-пряма. Ця межа близька, якщо m набагато більше від n, але при майже однакових m і n теорема Семереді — Троттера дає тіснішу межу $O(n^{2/3}m^{2/3}+n+m)$. Проте теорему Семереді — Троттера можна довести, поділивши точки й прямі на підмножини, для яких межі Коварі — Шош — Турана тісні.

Див. також

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

Література

• 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. — (Series A). — 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 (26 січня). — С. 280–290. — (Series B). — 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, MR0506522.
• 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.