Проблема Ружи – Семереди

Следующие вопросы имеют ответы, которые асисмптотически эквивалентны — они отличаются не более чем на постоянный множитель друг от друга[1]:

• Каково максимальное возможное число рёбер графа с ${\displaystyle n}$ вершинами, в которых любое ребро принадлежит единственному треугольнику?[2] Графы с этим свойством называются локально линейными графами[3] или локально паросочетаемыми графами[4].
• Каково максимальное возможное число рёбер в двудольном графе с ${\displaystyle n}$ вершинами на каждой стороне его доли, рёбра которого могут быть разбиты на ${\displaystyle n}$ порождённых подграфов, каждый из которых является паросочетанием[1]?
• Каково наибольшее число троек точек, которые можно выбрать из ${\displaystyle n}$ заданных точек, чтобы любые шесть точек содержали не более двух из отобранных троек?[5] Проблема Ружи – Семереди ищет ответ на эти эквивалентные вопросы.

Чтобы привести задачу порождённого паросочетания для двудольного графа в задачу единственного треугольника, добавляем множество из ${\displaystyle n}$ вершин графа, по одному для каждого порождённого паросочетания, и добавляем рёбра из вершин ${\displaystyle u}$ и ${\displaystyle v}$ двудольного графа в вершину ${\displaystyle w}$ в этом третьем множестве, когда ребро двудольного графа ${\displaystyle uv}$ принадлежит порождённому паросочетанию ${\displaystyle w}$. В результате получим сбалансированный трёхдольный граф с ${\displaystyle 3n}$ вершинами со свойством единственности треугольников. В другом направлении, любой граф со свойством единственности треугольников может быть приведён к сбалансированному трёхдольному графу путём распределения долей вершин по трём равным множествам случайно и с сохранением треугольников, которые задают распределение на доли. Это приводит к сохранению постоянного отношения треугольников и рёбер. Сбалансированный трёхдольный граф со свойством единственности треугольников может быть преобразован в разделённый двудольный граф путём удаления одного из его трёх подмножеств вершин, создавая порождённое паросочетание на соседях каждой из удалённых вершин.

Чтобы преобразовать граф с единственностью треугольника на ребро в систему троек, возьмём в качестве троек треугольники графа. Никакие шесть точек не могут включать три треугольника без того, чтобы или два из трёх треугольников имели общее ребро, или все три треугольника образуют четвёртый треугольник, который имеет общие рёбра с каждых из них. В другом направлении, для преобразования системы троек в граф, сначала исключим любые множества из четырёх точек, которые содержат две тройки. Эти четыре точки не могут присутствовать в других тройках, а потому не могут добавить более чем линейное число троек. Теперь формируем граф, соединяющий любую пару точек, которые принадлежат любой из оставшихся троек.

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

Для построения графа этого вида из свободного от арифметических прогрессий подмножества Беренда ${\displaystyle A}$, нумеруем вершины в каждой доле от ${\displaystyle 0}$ до ${\displaystyle p-1}$ и строим треугольники вида ${\displaystyle (x,x+a,x+2a)}$ по модулю ${\displaystyle p}$ для каждого ${\displaystyle x}$ из интервала от ${\displaystyle 0}$ до ${\displaystyle p-1}$ и каждое число ${\displaystyle a}$ принадлежит ${\displaystyle A}$. Например, с ${\displaystyle p=3}$ и ${\displaystyle A=\{\pm 1\}}$ в результате получим сбалансированный трёхдольный граф с 9 вершинами и 18 рёбрами, показанный на рисунке. Граф, образованный путём объединения этих треугольников, имеет желаемое свойство, что каждое ребро принадлежит ровно одному треугольнику. Если бы это было не так, существовал бы треугольник ${\displaystyle (x,x+a,x+a+b)}$, где ${\displaystyle a}$, ${\displaystyle b}$ и ${\displaystyle c=(a+b)/2}$ принадлежат ${\displaystyle A}$, что нарушает предположение об отсутствии арифметических прогрессий ${\displaystyle (a,c,b)}$ в ${\displaystyle A}$[5].

Лемма регулярности Семереди может быть использована для доказательства, что любое решение проблемы Ружи – Семереди имеет не более ${\displaystyle o(n^{2})}$ рёбер или треугольников[5]. Из более сильного врианта леммы об удалении графа Якоба Фокса следует, что размер решения не превосходит ${\displaystyle n^{2}/e^{\Omega (\log ^{*}n)}}$. Здесь ${\displaystyle o}$ и ${\displaystyle \Omega }$ являются представителями нотации «o малое» и ${\displaystyle \Omega }$, а ${\displaystyle \log ^{*}}$ означает итерированный логарифм. Фокс доказал, что в любом графе с ${\displaystyle n}$ вершинами и ${\displaystyle O(n^{3-\delta })}$ треугольниками для некоторого ${\displaystyle \delta >0}$ можно найти подграф без треугольников путём удаления не более ${\displaystyle n^{2}/e^{\Omega (\log ^{*}n)}}$ рёбер[7]. В графе со свойством единственности треугольников существует (естественно) ${\displaystyle O(n^{2})}$ треугольников, так что результат приходит с ${\displaystyle \delta =1}$. Но в этом графе каждое удаление ребра удаляет только один треугольник, так что число рёбер, которые следует удалить для исключения всех треугольников, равно числу треугольников.

Проблема названа именами Имре З. Ружи и Эндре Семереди, которые изучали данную проблему в формулировке троек точек в публикации 1978 года[5]. Однако проблему перед этим изучали У. Дж. Браун, Пал Эрдёш и Вера Т. Шош в двух публикациях в 1973, в которых доказывали, что максимальное число троек может быть ${\displaystyle \Omega (n^{3/2})}$[8], и высказали гипотезу, что на самом деле оно равно ${\displaystyle o(n^{2})}$[9]. Ружа и Семереди дали (неравные) почти квадратичные верхние и нижние границы для проблемы, существенно улучшающие нижнюю границу Брауна, Эрдёша и Соса и доказательство их гипотезы[5].

Упаковка треног, одно из приложений верхних границ проблемы Ружи – Семереди

Существование плотных графов, которые могут быть разбиты на большие порождённые паросочетания использовалось для построения эффективных тестов, является ли булевская функция линейной, ключевой компонент теоремы PCP в теории вычислительной сложности[10]. В теории алгоритмов проверки свойств известные результаты по проблеме Ружи – Семереди применялись для того, чтобы показать, что можно проверить, не содержит ли граф заданный подграф ${\displaystyle H}$ (с односторонней ошибкой по числу запросов, полиномиальных от параметра ошибки) тогда и только тогда, когда ${\displaystyle H}$ является двудольным графом[11].

В теории поточных алгоритмов для паросочетаний графа (например, для сопоставления рекламодателей с рекламными слотами), качество покрытия паросочетанием (разреженные подграфы, примерно сохраняющие размер паросочетаний во всех подмножествах вершин) тесно связано с плотностью двудольных графов, которые могут быть разбиты на порождённые паросочетания. Это построение использует модифицированную форму проблемы Ружи – Семереди, в которой число порождённых паросочетаний может быть много меньше числа вершин, но каждое порождённое паросочетание должно покрывать бо́льшую часть вершин графа. В этой версии проблемы можно построить графы с непостоянным числом порождённых паросочетаний линейного размера, а этот результат приводит к почти точным границам на аппроксимационный коэффициент для поточных алгоритмов сопоставления[12][13][14][15].

Подкадратичная верхняя граница проблемы Ружи – Семереди была также использована для получения границы ${\displaystyle o(3^{n})}$ на размер множеств колпаков[16] до того как были доказаны более сильные границы вида ${\displaystyle c^{n}}$ для ${\displaystyle c<3}$ для этой проблемы[17]. Она также обеспечивает лучшую известную верхнюю границу для упаковки треног[18].