Лемма об удалении гиперграфа

В теории графов лемма об удалении гиперграфа гласит, что когда гиперграф содержит несколько копий данного подгиперграфа, то все копии можно удалить, удалив небольшое количество гиперребер. Это обобщение леммы об удалении графа . Особый случай, когда граф представляет собой тетраэдр, известен как лемма об удалении тетраэдра . Впервые это доказали Нэгл, Рёдль, Шахт и Скокан. и независимо от Гауэрса.

Лемму об удалении гиперграфа можно использовать для доказательства таких результатов, как теорема Семереди. и многомерная теорема Семереди.

Заявление

Лемма об удалении гиперграфа утверждает, что для любого $\varepsilon ,r,m>0$, существует $\delta =\delta (\varepsilon ,r,m)>0$ такой, что для любого $r$-однородный гиперграф $H$ с $m$ вершин верно следующее: если $G$ есть ли какой-нибудь $n$-вершина $r$-однородный гиперграф с не более чем $\delta n^{v(H)}$ подграфы, изоморфные $H$, то можно удалить все копии $H$ от $G$ удалив максимум $\varepsilon n^{r}$ гиперребра из $G$.

Эквивалентная формулировка состоит в том, что для любого графа $G$ с $o(n^{v(H)})$ копии $H$, мы можем удалить все копии $H$ от $G$ удалив $o(n^{r})$ гиперребра.

Идея доказательства леммы об удалении гиперграфа.

Общая идея доказательства аналогична идее леммы об удалении графа . Мы доказываем гиперграфовую версию леммы Семереди о регулярности (разбиение гиперграфов на псевдослучайные блоки) и счетную лемму (оценка количества гиперграфов в соответствующем псевдослучайном блоке). Основная трудность доказательства состоит в определении правильного понятия регулярности гиперграфа. Было несколько попыток определить «разбиение» и «псевдослучайные (регулярные) блоки» в гиперграфе, но ни один из них не может дать строгую лемму о счете. Первое правильное определение леммы Семереди о регулярности гиперграфов общего назначения дано Рёдлем и др.

В лемме о регулярности Семереди разбиения выполняются по вершинам (1-гиперребро) для регулирования ребер (2-гиперребро). Однако для $k>2$, если мы просто будем регулировать $k$-гиперребра, используя только 1-гиперребро, мы потеряем информацию обо всех $j$-гиперребра посередине, где $1<j<k$, и не можем найти счетную лемму. Правильная версия должна разделить $(k-1)$-гиперребра для регулирования $k$-гиперребра. Чтобы получить больший контроль над $(k-1)$-гиперребра, мы можем пойти на уровень глубже и разделить $(k-2)$-гиперребра для их регулирования и т. д. В конечном итоге мы придем к сложной структуре регулирования гиперребер.

Идея доказательства для 3-однородных гиперграфов

Например, мы демонстрируем неформальную версию леммы Семереди о регулярности с 3-гиперграфами, впервые предложенную Франклом и Рёдлем. Рассмотрим разбиение ребер $E(K_{n})=G_{1}^{(2)}\cup \dots \cup G_{l}^{(2)}$ такой, что для большинства троек $(i,j,k),$ сверху много треугольников $\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right).$ Мы говорим, что $\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)$ является «псевдослучайным» в том смысле, что для всех подграфов $A_{i}^{(2)}\subset G_{i}^{(2)}$ с не слишком малым количеством треугольников сверху $\left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right),$ у нас есть

$\left|d\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)-d\left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right)\right|\leq \varepsilon ,$

где $d(X,Y,Z)$ обозначает долю $3$-равномерное гиперребро в $G^{(3)}$ среди всех треугольников на вершине $(X,Y,Z)$.

Затем мы далее определяем правильное разбиение как разбиение, в котором тройки нерегулярных частей составляют не более $\varepsilon$ доля всех троек частей в разбиении.

Помимо этого, нам необходимо продолжить регуляризацию $G_{1}^{(2)},\dots ,G_{l}^{(2)}$ через разбиение множества вершин. В результате мы имеем суммарные данные о регулярности гиперграфа следующим образом:

1. раздел $E(K_{n})$ в графы такие, что $G^{(3)}$ сидит псевдослучайно сверху;
2. раздел $V(G)$ такие, что графики в (1) являются чрезвычайно псевдослучайными (что напоминает лемму о регулярности Семереди ).

Доказав лемму о регулярности гиперграфа, мы можем доказать лемму о подсчете гиперграфов. Остальная часть доказательства проводится аналогично доказательству леммы об удалении графа .

Доказательство теоремы Семереди.

Позволять $r_{k}(N)$ быть размером наибольшего подмножества $\{1,\ldots ,N\}$ который не содержит длины $k$ арифметическая прогрессия. Теорема Семереди утверждает, что $r_{k}(N)=o(N)$ для любой константы $k$. Идея высокого уровня доказательства состоит в том, что мы строим гиперграф из подмножества без какой-либо длины. $k$ арифметической прогрессии, затем используйте лемму об удалении графа, чтобы показать, что этот граф не может иметь слишком много гиперребер, что, в свою очередь, показывает, что исходное подмножество не может быть слишком большим.

Позволять $A\subset \{1,\ldots ,N\}$ быть подмножеством, которое не содержит никакой длины $k$ арифметическая прогрессия. Позволять $M=k^{2}N+1$ быть достаточно большим целым числом. Мы можем подумать о $A$ как подмножество $\mathbb {Z} /M\mathbb {Z}$. Ясно, что если $A$ не имеет длины $k$ арифметическая прогрессия в $\mathbb {Z}$, он также не имеет длины $k$ арифметическая прогрессия в $\mathbb {Z} /M\mathbb {Z}$.

Мы построим $k$-игры $(k-1)$-однородный гиперграф $G$ от $A$ с частями $V_{1},V_{2},\ldots ,V_{k}$, все из которых $M$ наборы вершин элементов, индексированные $\mathbb {Z} /M\mathbb {Z}$. Для каждого $1\leq i\leq k$, добавляем гиперребро между вершинами $(v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}$ тогда и только тогда, когда $\sum _{j\neq i}(j-i)v_{j}\in A.$ Позволять $H$ быть полным $k$-игры $(k-1)$-однородный гиперграф. Если $G$содержит изоморфную копию $H$ с вершинами $v_{1},\ldots ,v_{k}$, затем $\alpha _{i}=\sum _{j\neq i}(j-i)v_{j}\in A$ для любого $1\leq i\leq j$. Однако обратите внимание, что $\alpha _{i}$ это длина $k$ арифметическая прогрессия с общей разностью $\alpha _{i+1}-\alpha _{i}=-\sum _{j}v_{j}$. С $A$ не имеет длины $k$ арифметической прогрессии, то должно быть так, что $\alpha _{1}=\cdots =\alpha _{k}$, так $\sum _{j}v_{j}=0$.

Таким образом, для каждого гиперребра $(v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}$, мы можем найти уникальную копию $H$ что это ребро лежит в нахождении $v_{i}=-\sum _{j\neq i}v_{j}$. Количество копий $H$ в $G$ равно ${\frac {1}{k}}e(G)=O(N^{k-1})=o(N^{k})$. Следовательно, по лемме об удалении гиперграфа мы можем удалить $o(N^{k-1})$ края, чтобы удалить все копии $H$ в $G$. Поскольку каждое гиперребро $G$ находится в уникальном экземпляре $H$, чтобы удалить все копии $H$ в $G$, нам нужно удалить как минимум $e(G)/k$ края. Таким образом, $e(G)=o(N^{k-1})$.

Количество гиперребер в $G$ является $kM^{k-2}|A|=o(N^{k-1})$, из чего делается вывод, что $|A|=o(N)$.

Этот метод обычно не дает хорошей количественной оценки, поскольку скрытые константы в лемме об удалении гиперграфа включают обратную функцию Аккермана. Для лучшей количественной оценки Гауэрс доказал, что $|A|\leq {\frac {N}{(\log \log N)^{c_{k}}}}$ для некоторой константы $c_{k}$ в зависимости от $k$. Это лучшая граница для $k\geq 5$ до сих пор.

Приложения

• Лемма об удалении гиперграфа используется для доказательства многомерной теоремы Семереди Дж. Солимози. Утверждается, что любое для любого конечного подмножества $S$ из $\mathbb {Z} ^{r}$, любой $\delta >0$ и любой $n$ достаточно большой, любое подмножество $[n]^{r}$ по крайней мере размером $\delta n^{r}$ содержит подмножество формы $a\cdot S+d$, то есть расширенная и переведенная копия $S$. Теорема об углах является частным случаем, когда $S=\{(0,0),(0,1),(1,0)\}$.
• Он также используется для доказательства полиномиальной теоремы Семереди, теоремы Семереди о конечном поле и теоремы Семереди о конечной абелевой группе.

См. также

• Лемма об удалении графа
• Теорема Семереди
• Задачи, связанные с арифметическими прогрессиями