Лемма об удалении гиперграфа - Hypergraph removal lemma

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

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

Заявление

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

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

Доказательство идеи

Идея доказательства на высоком уровне аналогична идее доказательства лемма об удалении графа. Мы доказываем гиперграф-версию Лемма Семереди о регулярности (разбиение гиперграфов на псевдослучайные блоки) и леммы о подсчете (оценка количества гиперграфов в соответствующем псевдослучайном блоке). Ключевая трудность доказательства состоит в том, чтобы определить правильное понятие регулярности гиперграфа. Было несколько попыток^{[3][4][5][6][7][8][9][10][11][12]} определить «разбиение» и «псевдослучайные (регулярные) блоки» в гиперграфе, но ни один из них не может дать сильную лемму о счете. Первое правильное определение леммы Семереди о регулярности для общих гиперграфов дано Rödl et al.^[2]

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

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

${\displaystyle \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 ,}$

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

Далее мы определяем регулярное разбиение как разбиение, в котором тройки нерегулярных частей составляют не более ${\displaystyle \varepsilon }$ фракция всех троек в разделе.

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

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

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

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

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

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

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

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

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

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

Приложения

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

Смотрите также

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

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

1. Гауэрс, Уильям (2007-11-01). «Регулярность гиперграфа и многомерная теорема Семереди». Анналы математики. 166 (3): 897–946. arXiv:0710.3032. Bibcode:2007arXiv0710.3032G. Дои:10.4007 / annals.2007.166.897. ISSN  0003-486X.
2. Rodl, V .; Nagle, B .; Skokan, J .; Schacht, M .; Кохаякава, Ю. (26 мая 2005 г.). «С обложки: метод регулярности гиперграфов и его приложения». Труды Национальной академии наук. 102 (23): 8109–8113. Bibcode:2005ПНАС..102.8109Р. Дои:10.1073 / pnas.0502771102. ISSN  0027-8424. PMID  15919821.
3. Хэвиленд, Джули; Томасон, Эндрю (май 1989 г.). «Псевдослучайные гиперграфы». Дискретная математика. 75 (1–3): 255–278. Дои:10.1016 / 0012-365x (89) 90093-9. ISSN  0012-365X.
4. Chung, F.R.K .; Грэм, Р. Л. (1989-11-01). «Квазислучайные гиперграфы». Труды Национальной академии наук. 86 (21): 8175–8177. Bibcode:1989PNAS ... 86.8175C. Дои:10.1073 / pnas.86.21.8175. ISSN  0027-8424. PMID  16594074.
5. Чунг, Фан Р. К. (1990). «Квазислучайные классы гиперграфов». Случайные структуры и алгоритмы. 1 (4): 363–382. Дои:10.1002 / rsa.3240010401. ISSN  1042-9832.
6. Chung, F.R.K .; Грэм, Р. Л. (1990). «Квазислучайные гиперграфы». Случайные структуры и алгоритмы. 1 (1): 105–124. Дои:10.1002 / rsa.3240010108. ISSN  1042-9832. ЧВК  298241. PMID  16594074.
7. Chung, F.R.K .; Грэм, Р. Л. (январь 1991 г.). «Квазислучайные системы множеств». Журнал Американского математического общества. 4 (1): 151. Дои:10.2307/2939258. ISSN  0894-0347. JSTOR  2939258.
8. Кохаякава, Йошихару; Рёдль, Войтех; Скокан, Йозеф (февраль 2002 г.). «Гиперграфы, квазислучайность и условия регулярности». Журнал комбинаторной теории, серия А. 97 (2): 307–352. Дои:10.1006 / jcta.2001.3217. ISSN  0097-3165.
9. Frieze, Алан; Каннан, Рави (1 февраля 1999). «Быстрое приближение к матрицам и приложениям». Комбинаторика. 19 (2): 175–220. Дои:10.1007 / s004930050052. ISSN  0209-9683.
10. Чигринов, Анджей; Рёдль, Войтех (январь 2000 г.). «Лемма об алгоритмической регулярности гиперграфов». SIAM Журнал по вычислениям. 30 (4): 1041–1066. Дои:10.1137 / s0097539799351729. ISSN  0097-5397.
11. Чанг, Фань Р.К. (2007-07-05). «Леммы о регулярности гиперграфов и квазислучайности». Случайные структуры и алгоритмы. 2 (2): 241–252. Дои:10.1002 / RSA.3240020208. ISSN  1042-9832.
12. Frankl, P .; Рёдль, В. (декабрь 1992 г.). «Лемма о равномерности гиперграфов». Графы и комбинаторика. 8 (4): 309–312. Дои:10.1007 / bf02351586. ISSN  0911-0119.
13. Нэгл, Брендан; Рёдль, Войтех (17 июля 2003 г.). «Свойства регулярности для тройных систем». Случайные структуры и алгоритмы. 23 (3): 264–332. Дои:10.1002 / rsa.10094. ISSN  1042-9832.
14. Франкл, Питер; Рёдль, Войтех (7 февраля 2002 г.). «Экстремальные задачи на системах множеств». Случайные структуры и алгоритмы. 20 (2): 131–164. Дои:10.1002 / rsa.10017. ISSN  1042-9832.
15. Гауэрс, У. Т. (1 июля 1998 г.). «Новое доказательство теоремы Семереди для арифметических прогрессий длины четыре». Геометрический и функциональный анализ. 8 (3): 529–551. Дои:10.1007 / с000390050065. ISSN  1016-443X.
16. СОЛИМОСИ, Дж. (Март 2004 г.). «Записка по вопросу об Эрдёше и Грэме». Комбинаторика, теория вероятностей и вычисления. 13 (2): 263–267. Дои:10.1017 / s0963548303005959. ISSN  0963-5483.
17. Бергельсон, Виталий; Лейбман, Александр; Циглер, Тамар (февраль 2011 г.). «Сдвинутые простые числа и многомерные Семереди и полиномиальные теоремы Ван дер Вардена». Comptes Rendus Mathématique. 349 (3–4): 123–125. arXiv:1007.1839. Дои:10.1016 / j.crma.2010.11.028. ISSN  1631-073X.
18. Furstenberg, H .; Кацнельсон, Ю. (декабрь 1991 г.). "Версия плотности теоремы Хейлса-Джеветта". Журнал д'анализа математика. 57 (1): 64–119. Дои:10.1007 / bf03041066. ISSN  0021-7670.