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

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

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

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

Двочастковий граф ${\displaystyle G=(U,V,E)}$ складається з двох множин вершин ${\displaystyle U}$ і ${\displaystyle V}$, що не перетинаються, і множини ребер, кожне з яких з'єднує вершину з ${\displaystyle U}$ з вершиною з ${\displaystyle V}$. Жодні два ребра не можуть з'єднувати ту саму пару вершин. Повний двочастковий граф — це двочастковий граф, у якому кожна пара вершин (одна вершина з ${\displaystyle U}$, інша з ${\displaystyle V}$) пов'язана ребром. Повний двочастковий граф, у якому множина ${\displaystyle U}$ має ${\displaystyle s}$ вершин, а ${\displaystyle V}$ має ${\displaystyle t}$ вершин, позначають ${\displaystyle K_{s,t}}$. Якщо ${\displaystyle G=(U,V,E)}$ — двочастковий і існують підмножини ${\displaystyle s}$ вершин множини ${\displaystyle U}$ і ${\displaystyle t}$ вершин множини ${\displaystyle V}$, такі, що всі вершини цих двох множин пов'язані одна з одною, ці вершини утворюють породжений підграф вигляду ${\displaystyle K_{s,t}}$. (Тут порядок ${\displaystyle s}$ і ${\displaystyle t}$ істотний — множина вершин ${\displaystyle s}$ має належати ${\displaystyle U}$, а множина вершин ${\displaystyle t}$ має належати ${\displaystyle V}$.)

Функція Заранкевича ${\displaystyle z(m,n;s,t)}$ позначає найбільшу можливу кількість ребер у двочастковому графі ${\displaystyle G=(U,V,E)}$, для якого ${\displaystyle |U|=m}$ та ${\displaystyle |V|=n}$, який не містить підграфа вигляду ${\displaystyle K_{s,t}}$. Випадок ${\displaystyle z(n,n;t,t)}$ для стислості записують ${\displaystyle z(n;t)}$. Задання Заранкевича ставить питання про формулу для функції Заранкевича, або (якщо таку формулу встановити не вдасться), про тісні асимптотичні межі швидкості зростання ${\displaystyle z(n;t)}$ у припущенні, що ${\displaystyle t}$ фіксоване, а ${\displaystyle n}$ прямує до нескінченності.

Для ${\displaystyle s=t=2}$ ця задача збігається із задачею визначення кліток із обхватом шість. Задача Заранкевича, клітки та скінченні геометрії сильно взаємопов'язані[3].

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

Приклади

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

Число ${\displaystyle z(n;2)}$ відповідає найбільшому числу ребер у двочастковому графі з ${\displaystyle n}$ вершинами у кожній частці, що не має циклів довжини 4 (його обхват не менше шести). Тоді ${\displaystyle z(2;2)=3}$ (досягається на шляху з трьох дуг), а ${\displaystyle z(3;2)=6}$ (шестикутник).

В оригінальному формулюванні задачі Заранкевич ставив питання про значення ${\displaystyle z(n;3)}$ для ${\displaystyle n=4,5}$ та ${\displaystyle 6}$. Незабаром Вацлав Серпінський дав відповіді: ${\displaystyle z(4;3)=13}$, ${\displaystyle z(5;3)=20}$ та ${\displaystyle z(6;3)=26}$[4]. Випадок ${\displaystyle z(4;3)}$ відносно простий — двочастковий граф з 13 ребрами і чотирма вершинами в кожній частці, що не містить підграфа ${\displaystyle K_{3,3}}$, можна отримати додаванням довгої діагоналі до графа куба. І навпаки, якщо двочастковий граф із 14 ребрами має по чотири вершини в кожній частці, дві вершини на кожній стороні повинні мати степінь чотири. Видалення цих чотирьох вершин і інцидентних їм 12 ребер залишає множину порожніх ребер, кожне з яких разом з чотирма видаленими вершинами утворює підграф ${\displaystyle K_{3,3}}$.

Верхні межі

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

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

Насправді Коварі, Шош і Туран довели відповідну нерівність для ${\displaystyle z(n;t)}$, але незабаром після цього Хілтен-Кавалліус зауважив, що такі ж аргументи можна використати для доведення загального випадку[6]. Штефан Знам^[en] поліпшив сталий множник у правій частині формули для випадку ${\displaystyle z(n;t)}$[7]:

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

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

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

і

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

Нижні межі

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

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

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

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

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

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

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

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

З точністю до сталого множника ${\displaystyle z(n;t)}$ обмежує також число ребер графа з ${\displaystyle n}$ вершинами (не обов'язково двочасткового), який не містить підграфа ${\displaystyle K_{t,t}}$. З одного боку, двочастковий граф із ${\displaystyle z(n;t)}$ ребрами та ${\displaystyle n}$ вершинами в кожній частці можна зменшити до графа з ${\displaystyle n}$ вершинами та ${\displaystyle z(n;t)/4}$ ребрами, вибравши випадково ${\displaystyle n/2}$ із числа всіх вершин графа. З іншого боку, граф з ${\displaystyle n}$ вершинами без підграфів ${\displaystyle K_{t,t}}$ можна перетворити на двочастковий граф із ${\displaystyle n}$ вершинами в кожній частці і подвоєним числом ребер, який, як і раніше, не міститиме ${\displaystyle K_{t,t}}$ як підграф, побудувавши його двочасткове подвійне накриття^[en][14].

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

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

Див. також

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

Примітки

1. Bollobás, 2004, с. 309–326.
2. Zarankiewicz, 1951, с. 301.
3. Tamás Héger, Tamás Szőnyi, Gábor Damásdi (19 березня 2013). The Zarankiewicz problem, cages, and geometries (pdf) (англ.). Будапештський університет. Архів (PDF) оригіналу за 4 березня 2016. Процитовано 25 травня 2017. {{cite web}}: Cite має пустий невідомий параметр: |description= (довідка)
4. Sierpiński, 1951, с. 173–174.
5. Kővári et al, 1954, с. 50–57.
6. Hyltén-Cavallius, 1958, с. 59–65.
7. Znám, 1963, с. 81–84.
8. Reiman, 1958, с. 269–273.
9. Bollobás, 2004, с. 313, Corollary 2.7.
10. Füredi, 1996, с. 141–144.
11. Brown, 1966, с. 281–285.
12. Bollobás, 2004, с. 312, Conjecture 15.
13. Alon et al, 1999, с. 280–290.
14. Bollobás, (2004), Theorem 2.3, p. 310.
15. Matoušek, 2002, с. 65–68.

Література

• 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 (27 грудня). — С. 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.