Задача Ружі — Семереді

Задача Ружі — Семереді або (6,3)-проблема запитує про найбільшу кількість ребер у графі, в якому будь-яке ребро належить єдиному трикутнику. Еквівалентно, задача запитує про найбільшу кількість ребер у збалансованому двочастковому графі, ребра якого можна розбити на лінійну кількість породжених парувань, або найбільшу кількість трійок, які можна вибрати з $n$ точок так, що кожні шість точок містять максимум дві трійки. Задачу названо іменами Імре З. Ружі та Ендре Семереді, які першими довели, що відповідь менша, ніж $n^{2}$ на множник, що повільно зростає (але поки невідомий).

Граф Пелі з дев'ятьма вершинами, збалансований тричастковий граф з 18 ребрами, кожне з яких належить одному трикутнику.

Деякі малюнки графа Брауера — Хемерса, не тричасткового 20-регулярного графа з 81 вершиною, в якому кожне ребро належить рівно одному трикутнику

Еквівалентність формулювань

Такі питання мають відповіді, які асимптотично еквівалентні — вони відрізняються одна від одної не більше ніж на сталий множник:

• Яке найбільше можливе число ребер графа з $n$ вершинами, у якого будь-яке ребро належить єдиному трикутнику? Графи з цією властивістю називаються локально лінійними графами або локально парваними графами.
• Яке найбільше можливе число ребер у двочастковому графі з $n$ вершинами в кожній з його часток, ребра якого можна розбити на $n$ породжених підграфів, кожен з яких є паруванням?
• Яке найбільше число трійок точок, які можна вибрати з $n$ заданих точок, щоб будь-які шість точок містили не більше двох із відібраних трійок?

Задача Ружі — Семереді шукає відповідь ці еквівалентні питання.

Щоб звести задачу породженого парування для двочасткового графа до задачі єдиного трикутника, додаємо до графа множину з $n$ вершин, по одній для кожного породженого парування, і додаємо ребра з вершин $u$ і $v$ двочасткового графа до вершини $w$ в цій третій множині, коли ребро двочасткового графа $uv$ належить породженому паруванню $w$. Результатом буде збалансований тричастковий граф з $3n$ вершинами зі властивістю єдиності трикутників. З іншого боку, будь-який граф зі властивістю єдиності трикутників можна звести до збалансованого тричасткового графа, поділивши частки вершин на три рівних множини випадково і зберігши лише трикутники, які задають розподіл на частки. Це приводить до збереження сталого відношення трикутників та ребер. Збалансований тричастковий граф зі властивістю єдиності трикутників можна перетворити на розділений двочастковий граф видаленням однієї з трьох підмножин його вершин, створивши породжене парування на сусідах кожної з видалених вершин.

Щоб перетворити граф з єдиністю трикутника на ребро в систему трійок, візьмемо як трійки трикутники графа. Ніякі шість точок не можуть включати три трикутники без того, щоб або два з трьох трикутників мали спільне ребро, або всі три трикутники утворили четвертий трикутник, який має спільні ребра з кожним із них. І навпаки, для перетворення системи трійок у граф, спочатку виключимо будь-які множини з чотирьох точок, які містять дві трійки. Ці чотири точки не можуть бути присутніми в інших трійках, тому не можуть додати більш ніж лінійне число трійок. Тепер формуємо граф, що з'єднує будь-яку пару точок, які належать будь-якій із решти трійок.

Нижня межа

Майже квадратичну межу для задачі Ружі — Семереді можна отримати з результату Фелікса Беренда, за яким числа за модулем непарного простого числа $p$ мають великі множини Салема — Спенсера, підмножини $A$ розміру $|A|=p/e^{O({\sqrt {\log p}})}$ без тричленних арифметичних прогресій. Результат Беренда можна використати для побудови тричасткових графів, у яких кожна частка має $p$ вершин, граф містить $3|A|p$ ребер та кожне ребро належить єдиному трикутнику. Тоді, за цією побудовою, $n=3p$ і число ребер дорівнює $n^{2}/e^{O({\sqrt {\log n}})}$.

Для побудови графа цього виду з вільної від арифметичних прогресій підмножини Беренда $A$ нумеруємо вершини в кожній частці від $0$ до $p-1$ і будуємо трикутники вигляду $(x,x+a,x+2a)$ за модулем $p$ для кожного $x$ з інтервалу від $0$ до $p-1$ і кожного числа $a$, що належить $A$. Наприклад, з $p=3$ і $A=\{\pm 1\}$ в результаті отримаємо збалансований тричастковий граф з 9 вершинами та 18 ребрами, показаний на малюнку. Граф, утворений об'єднанням цих трикутників, має бажану властивість, що кожне ребро належить рівно одному трикутнику. Якби це було не так, існував би трикутник $(x,x+a,x+a+b)$, де $a$, $b$ і $c=(a+b)/2$ належать $A$, що порушує припущення про відсутність арифметичних прогресій $(a,c,b)$ в $A$.

Верхня межа

Для доведення, що будь-який розв'язок задачі Ружі — Семереді має не більше $o(n^{2})$ ребер або трикутників можна використати лему регулярності Семереді. Зі сильнішого варіанта леми про видалення графа Якоба Фокса випливає, що розмір розв'язку не перевищує $n^{2}/e^{\Omega (\log ^{*}n)}$. Тут $o$ і $\Omega$ — елементи нотації «o мале» та $\Omega$, а $\log ^{*}$ означає ітерований логарифм. Фокс довів, що в будь-якому графі з $n$ вершинами та $O(n^{3-\delta })$ трикутниками для деякого $\delta >0$ можна знайти підграф без трикутників, видаливши не більше $n^{2}/e^{\Omega (\log ^{*}n)}$ ребер. У графі з властивістю єдиності трикутників існує (природно) $O(n^{2})$ трикутників, так що результат отримуємо з $\delta =1$. Але в цьому графі кожне видалення ребра видаляє лише один трикутник, так що число ребер, які слід видалити для виключення всіх трикутників, дорівнює кількості трикутників.

Історія

Задачу названо іменами Імре З. Ружі та Ендре Семереді, які вивчали її у формулюванні трійок точок у публікації 1978 року. Проте задачу перед цим вивчали У. Дж. Браун, Пал Ердеш та Віра Т. Шош у двох публікаціях (1973), у яких доводили, що найбільша кількість трійок може бути $\Omega (n^{3/2})$, і висловили гіпотезу, що насправді воно дорівнює $o(n^{2})$. Ружа і Семереді дали (нерівні) майже квадратичні верхні та нижні межі для задачі, що істотно покращують нижню межу Брауна, Ердеша та Шош та довівши їхню гіпотезу.

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

Пакування триног, одне з застосувань верхніх меж задачі Ружі — Семереді

Існування щільних графів, які можна розбити на великі породжені парування, використано для побудови ефективних тестів, чи є булівська функція лінійною, ключовий компонент теореми PCP в теорії обчислювальної складності. У теорії алгоритмів перевірки властивостей відомі результати щодо задачі Ружі — Семереді застосовано для того, щоб показати, що можна перевірити, чи містить граф заданий підграф $H$ (з однобічною похибкою кількості запитів, поліноміальною від параметра похибки) тоді й лише тоді, коли $H$ є двочастковим графом.

У теорії потокових алгоритмів для парувань графа (наприклад, для зіставлення рекламодавців з рекламними слотами), якість покриття паруванням (розріджені підграфи, які приблизно зберігають розмір парувань у всіх підмножинах вершин) тісно пов'язані зі щільністю двочасткових графів, які можна розбити на породжені парування. Ця побудова використовує модифіковану форму задачі Ружі — Семереді, в якій число породжених парувань може бути значно меншим від числа вершин, але кожне породжене парування має покривати більшу частину вершин графа. У цій версії задачі можна побудувати графи з несталим числом породжених парувань лінійного розміру, а цей результат приводить до майже точних меж на апроксимаційний коефіцієнт для потокових алгоритмів зіставлення.

Підквадратичну верхню межу задачі Ружі — Семереді використано також для отримання межі $o(3^{n})$ на розмір множин ковпаків до того, як для цієї задачі було доведено сильніші межі вигляду $c^{n}$ для $c<3$. Вона також забезпечує найкращу відому верхню межу для пакування триног.