Проблема Ружи – Семереди - Ruzsa–Szemerédi problem

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

Несколько видов График Брауэра – Хемерса, нетрехдольный 20-регулярный граф с 81 вершиной, в котором каждое ребро принадлежит ровно одному треугольнику

В комбинаторная математика и экстремальная теория графов, то Проблема Ружи – Семереди или же (6,3) -задача запрашивает максимальное количество ребер в графе, в котором каждое ребро принадлежит уникальному треугольнику, эквивалентно максимальное количество ребер в сбалансированном двудольном графе, ребра которого можно разделить на линейное число индуцированные соответствия, или максимальное количество троек, которое можно выбрать ${ displaystyle n}$ точек так, чтобы каждые шесть точек содержали не более двух троек. Проблема названа в честь Имре З. Ружа и Эндре Семереди, который первым доказал, что его ответ меньше, чем ${ Displaystyle п ^ {2}}$ медленно растущим (но пока неизвестным) фактором.^[1]

Эквивалентность составов

На следующие вопросы есть ответы, которые асимптотически эквивалент: они отличаются друг от друга максимум на постоянные факторы.^[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 п ^ {2} / е ^ {О ({ sqrt { log n}})}}$.^[5]

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

Верхняя граница

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

История

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

Приложения

Упаковка штатива, одно из приложений оценок сверху для задачи Ружи – Семереди

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

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

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

Рекомендации