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

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

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

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

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

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

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

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

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

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

Нижня межа

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

Для побудови графа цього виду з вільної від арифметичних прогресій підмножини Беренда $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$Шаблон:R.

Верхня межа

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

Історія

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

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

Шаблон:Не перекладено, одне з застосувань верхніх меж задачі Ружі — Семереді

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

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

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