Метод регулярности гиперграфа

В математике метод регулярности гиперграфа является мощным инструментом в экстремальной теории графов , который относится к комбинированному применению леммы о регулярности гиперграфа и связанной с ней леммы о подсчете. Это обобщение метода регулярности графа, которое относится к использованию регулярности Семереди и лемм о подсчете.

Очень неформально, лемма о регулярности гиперграфа разлагает любые заданные $k$-однородный гиперграф в случайный объект с ограниченными частями (с соответствующими понятиями ограниченности и случайности), с которым обычно легче работать. С другой стороны, лемма о подсчете гиперграфов оценивает количество гиперграфов данного класса изоморфизма в некоторых наборах случайно подобных частей. Это расширение леммы Семереди о регулярности , которая разбивает любой данный граф на части с ограниченным числом, так что ребра между частями ведут себя почти случайно. Точно так же лемма о подсчете гиперграфов является обобщением леммы о подсчете графов , которая оценивает количество копий фиксированного графа как подграфа большего графа.

Существует несколько различных формулировок метода, каждая из которых подразумевает лемму об удалении гиперграфа и ряд других мощных результатов, таких как теорема Семереди , а также некоторые из ее многомерных расширений. Следующие формулировки принадлежат В. Рёдлю , Б. Нэглу, Дж. Скокану, М. Шахту и Ю. Кохаякаве : альтернативные версии см. Тао (2006), и Гауэрс (2007).

Определения

Чтобы формально сформулировать регулярность гиперграфа и леммы о счете, нам необходимо определить несколько весьма технических терминов для формализации соответствующих понятий псевдослучайности (случайности) и ограниченности, а также для описания случайноподобных блоков и разбиений.

Обозначения

• $K_{j}^{(k)}$ обозначает $k$-равномерный клик по $j$ вершины.
• ${\mathcal {G}}^{(j)}$ это $l$-игры $j$-граф на вершинном разделе ${\mathcal {G}}^{(1)}=V_{1}\sqcup \ldots \sqcup V_{l}$.
• ${\mathcal {K}}_{j}({\mathcal {G}}^{(i)})$ это семья всех $j$Наборы вершин -элементов, охватывающие клику $K_{j}^{(i)}$ в ${\mathcal {G}}^{(i)}$. В частности, ${\mathcal {K}}_{j}({\mathcal {G}}^{(1)})=K_{l}^{(j)}(V_{1},\ldots ,V_{l})$ является полным $l$-игры $j$-граф.

Ниже определяется важное понятие относительной плотности, которое примерно описывает долю $j$-ребра, охватываемые $(j-1)$-ребра, находящиеся в гиперграфе. Например, когда $j=3$, количество $d({\mathcal {G}}^{(3)}\vert \mathbf {Q} ^{(2)})$ равен доле треугольников, образованных 2-ребрами в подгиперграфе, которые являются 3-ребрами.

Определение [Относительная плотность]. Для $j\geq 3$, исправьте некоторые классы $V_{i_{1}},\ldots ,V_{i_{j}}$ из ${\mathcal {G}}^{(1)}$ с $1\leq i_{1}<\ldots <i_{j}\leq l$. Предполагать $r\geq 1$ является целым числом. Позволять $\mathbf {Q} ^{(j-1)}=\{Q_{1}^{(j-1)},\ldots ,Q_{r}^{(j-1)}\}$ быть подгиперграфом индуцированного $j$- график совпадений ${\mathcal {G}}^{(j-1)}[V_{i_{1}},\ldots ,V_{i_{j}}]$. Определить относительную плотность $d\left({\mathcal {G}}^{(j)}\vert \mathbf {Q} ^{(j-1)}\right)={\frac {\left|{\mathcal {G}}^{(j)}\cap \cup _{s\in [r]}{\mathcal {K}}_{j}(Q_{s}^{j-1})\right|}{\left|\cup _{s\in [r]}{\mathcal {K}}_{j}(Q_{s}^{j-1})\right|}}$.

Далее следует подходящее понятие псевдослучайности, которое будет использовать метод регулярности. Неформально, согласно этой концепции регулярности, $(j-1)$-края ( ${\mathcal {G}}^{(j-1)}$) иметь некоторый контроль над $j$-края ( ${\mathcal {G}}^{(j)}$). Точнее, это определяет настройку, при которой плотность $j$ Ребра в больших подгиперграфах примерно такие же, как и следовало ожидать, исходя только из относительной плотности. Формально,

Определение [( $\delta _{j},d_{j},r$)-регулярность]. Предполагать $\delta _{j},d_{j}$ являются положительными действительными числами и $r\geq 1$ является целым числом. ${\mathcal {G}}^{(j)}$ является ( $\delta _{j},d_{j},r$)-регулярно относительно ${\mathcal {G}}^{(j-1)}$ если для любого выбора классов $V_{i_{1}},\ldots ,V_{i_{j}}$ и любой набор подгиперграфов $\mathbf {Q} ^{(j-1)}=\{Q_{1}^{(j-1)},\ldots ,Q_{r}^{(j-1)}\}$ из ${\mathcal {G}}^{(j-1)}[V_{i_{1}},\ldots ,V_{i_{j}}]$ удовлетворяющий $\left|\cup _{s\in [r]}{\mathcal {K}}_{j}(Q_{s})^{(j-1)}\right|\geq \delta _{j}\left|{\mathcal {K}}_{j}({\mathcal {G}}^{(j-1)}[V_{i_{1}},\ldots ,V_{i_{j}}])\right|$ у нас есть $d({\mathcal {G}}^{(j)}\vert \mathbf {Q} ^{(j-1)})=d_{j}\pm \delta _{j}$.

Грубо говоря, ниже описываются псевдослучайные блоки, на которые лемма о регулярности гиперграфа разбивает любой достаточно большой гиперграф. В регулярности Семереди 2-ребра регуляризованы по сравнению с 1-ребрами (вершинами). В этом обобщенном понятии $j$-ребра регуляризованы по сравнению с $(j-1)$- края для всех $2\leq j\leq h$. Точнее, это определяет понятие регулярного гиперграфа, называемого $(l,h)$-комплекс, в котором существует $j$-edge подразумевает существование всех лежащих в основе $(j-1)$-ребра, а также их относительную регулярность. Например, если $\{x,y,z\}$ является 3-ребром, то $\{x,y\}$, $\{x,z\}$, и $\{y,z\}$ являются 2-ребрами в комплексе. Более того, плотность 3-ребер во всех возможных треугольниках, образованных 2-ребрами, примерно одинакова в каждом наборе подгиперграфов.

Определение [ $(\delta ,\mathbf {d} ,r)$-обычный $(l,h)$-сложный]. Ан $(l,h)$-сложный $\mathbf {G}$ это система $\{{\mathcal {G}}^{(j)}\}_{j=1}^{h}$ из $l$-игры $j$ графики ${\mathcal {G}}^{(j)}$ удовлетворяющий ${\mathcal {G}}^{(j)}\subset {\mathcal {K}}_{j}({\mathcal {G}}^{(j-1)})$. Даны векторы положительных действительных чисел $\delta =(\delta _{2},\ldots ,\delta _{h})$, $\mathbf {d} =(d_{2},\ldots ,d_{h})$и целое число $r\geq 1$, мы говорим $(l,h)$-комплекс это $(\delta ,\mathbf {d} ,r)$-обычный, если

• Для каждого $1\leq i_{1}<i_{2}\leq l$, ${\mathcal {G}}^{(2)}[V_{i_{1}},V_{i_{2}}]$ является $\delta _{2}$-регулярный по плотности $d_{2}\pm \delta _{2}$.
• Для каждого $3\leq j\leq h$, ${\mathcal {G}}^{(j)}$ является ( $\delta _{j},d_{j},r$)-регулярно относительно ${\mathcal {G}}^{(j-1)}$.

Ниже описывается справедливое разделение, которое будет индуцировано леммой о регулярности гиперграфа. А $(\mu ,\delta ,\mathbf {d} ,r)$-справедливое семейство разбиений представляет собой последовательность разбиений 1-ребер (вершин), 2-ребер (пар), 3-ребер (троек) и т. д. В этом состоит важное отличие от разбиения, полученного по лемме о регулярности Семереди, где только вершины разбиваются. На самом деле, Гауэрс продемонстрировал, что одно лишь разбиение вершин не может дать достаточно сильного понятия регулярности, чтобы подразумевать лемму о подсчете гиперграфов.

Определение [ $(\mu ,\delta ,\mathbf {d} ,r)$-справедливый раздел]. Позволять $\mu >0$ быть действительным числом, $r\geq 1$ быть целым числом, и $\delta =(\delta _{2},\ldots ,\delta _{k-1})$, $\mathbf {d} =(d_{2},\ldots ,d_{k-1})$ быть векторами положительных вещественных чисел. Позволять $\mathbf {a} =(a_{1},\ldots ,a_{k-1})$ быть вектором положительных целых чисел и $V$ быть $n$-элементный набор вершин. Мы говорим, что семейство разбиений ${\mathcal {P}}={\mathcal {P}}(k-1,\mathbf {a} )=\{{\mathcal {P}}^{(1)}\,\ldots ,{\mathcal {P}}^{(k-1)}\}$ на $V$ является $(\mu ,\delta ,\mathbf {d} ,r)$-справедливым, если он удовлетворяет следующим условиям:

• ${\mathcal {P}}^{(1)}=\{V_{i}\colon i\in [a_{1}]\}$ является равноправным вершинным разбиением $V$. То есть $|V_{1}|\leq \ldots \leq |V_{a_{1}}|\leq |V_{1}|+1$ .
• ${\mathcal {P}}^{(j)}$ перегородки ${\mathcal {K}}_{j}({\mathcal {G}}^{(1)})=K_{a_{1}}^{(j)}(V_{1},\ldots ,V_{a_{1}})$ так что если $P_{1}^{(j-1)},\ldots ,P_{j}^{(j-1)}\in {\mathcal {P}}^{(j-1)}$ и ${\mathcal {K}}_{j}(\cup _{i=1}^{j}P_{i}{(j-1)})\neq \emptyset$ затем ${\mathcal {K}}_{j}(\cup _{i=1}^{j}P_{i}{(j-1)})$ делится не более чем на $a_{j}$ части, все из которых являются членами ${\mathcal {P}}^{(j)}$.

• Для всех, кроме большинства $\mu n^{k}$ $k$-кортежи $K\in {\binom {V}{k}}$ есть уникальный $(\delta ,\mathbf {d} ,r)$-обычный $(k,k-1)$-сложный $\mathbf {P} =\{P^{(j)}\}_{j=1}^{k-1}$ такой, что $P^{(j)}$ имеет в качестве членов ${\binom {k}{j}}$ разные классы разделов из ${\mathcal {P}}^{(j)}$ и $K\in {\mathcal {K}}_{k}(P^{(k-1)})\subset \ldots \subset {\mathcal {K}}_{k}(P^{(1)})$.

Наконец, следующее определяет, что это означает для $k$-однородный гиперграф должен быть регулярным относительно разбиения. В частности, это основное определение, которое описывает результат леммы о регулярности гиперграфа ниже.

Определение [Регулярность относительно разбиения]. Мы говорим, что $k$-график ${\mathcal {H}}^{(k)}$ является $(\delta _{k},r)$-регулярный относительно семейства разбиений ${\mathcal {P}}$ если все, кроме максимум $\delta _{k}n^{k}$ $k-$края $K$ из ${\mathcal {H}}^{(k)}$ иметь собственность, которая $K\in {\mathcal {K}}_{k}({\mathcal {G}}^{(1)})$ и если $\mathbf {P} =\{P^{(j)}\}_{j=1}^{k-1}$ уникален $(k,k-1)$-комплекс, для которого $K\in {\mathcal {K}}_{k}(P^{(k-1)})$, затем ${\mathcal {H}}^{(k)}$ является $(\delta _{k},d({\mathcal {H}}^{(k)}\vert P^{(k-1)}),r)$ регулярен по отношению к ${\mathcal {P}}$.

Заявления

Лемма о регулярности гиперграфа

За все позитивное настоящее $\mu$, $\delta _{k}$и функции $r\,\colon \mathbb {N} \times (0,1]^{k-2}\to \mathbb {N}$, $\delta _{j}\,\colon (0,1]^{k-j}\to (0,1]$ для $j=2,\ldots ,k-1$ существует $T_{0}$ и $n_{0}$ так что справедливо следующее. Для любого $k$-однородный гиперграф ${\mathcal {H}}^{(k)}$ на $n\geq n_{0}$ вершин, существует семейство разбиений ${\mathcal {P}}={\mathcal {P}}(k-1,\mathbf {a} )$ и вектор $\mathbf {d} =(d_{2},\ldots ,d_{k-1})$ так что для $r=r(a_{1},\mathbf {d} )$ и $\mathbf {\delta } =(\delta _{2},\ldots ,\delta _{k-1})$ где $\delta _{j}=\delta _{j}(d_{j},\ldots ,d_{k-1})$ для всех $j$, имеет место следующее.

• ${\mathcal {P}}$ это $(\mu ,\mathbf {\delta } ,\mathbf {d} ,r)$-справедливое семейство перегородок и $a_{i}\leq T_{0}$ для каждого $i=1,\ldots ,k-1$.
• ${\mathcal {H}}^{(k)}$ является $(\delta _{k},r)$ регулярен по отношению к ${\mathcal {P}}$.

Лемма о подсчете гиперграфов

Для всех целых чисел $2\leq k\leq l$ имеет место следующее: $\forall \gamma >0\;\;\forall d_{k}>0\;\;\exists \delta _{k}>0\;\;\forall d_{k-1}>0\;\;\exists \delta _{k-1}>0\;\cdots \;\forall d_{2}>0\;\;\exists \delta _{2}>0$ и есть целые числа $r$ и $m_{0}$ так что с $\mathbf {d} =(d_{2},\ldots ,d_{k})$, $\delta =(\delta _{2},\ldots ,\delta _{k})$, и $m\geq m_{0}$,

если $\mathbf {G} =\{{\mathcal {G}}^{(j)}\}_{j=1}^{k}$ это $(\delta ,\mathbf {d} ,r)$-обычный $(l,k)$ комплекс с вершинным разбиением ${\mathcal {G}}^{(1)}=V_{1}\cup \cdots \cup V_{l}$ и $|V_{i}|=m$, затем

$\left|{\mathcal {K}}_{l}({\mathcal {G}}^{(k)})\right|=(1\pm \gamma )\prod _{h=2}^{k}d_{h}^{\binom {l}{h}}\times m^{l}$.

Приложения

Основное применение, которому следуют большинство других, — это лемма об удалении гиперграфа , которая грубо утверждает, что при фиксированных ${\mathcal {F}}^{(k)}$ и большой ${\mathcal {H}}^{(k)}$ $k$-однородные гиперграфы, если ${\mathcal {H}}^{(k)}$ содержит мало копий ${\mathcal {F}}^{(k)}$, то можно удалить несколько гиперребер в ${\mathcal {H}}^{(k)}$ удалить все копии ${\mathcal {F}}^{(k)}$. Если выразить это более формально,

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

Для всех $l\geq k\geq 2$ и каждый $\mu >0$, существует $\zeta >0$ и $n_{0}>0$ так что справедливо следующее. Предполагать ${\mathcal {F}}^{(k)}$ это $k$-однородный гиперграф на $l$ вершины и ${\mathcal {H}}^{(k)}$ это на $n\geq n_{0}$ вершины. Если ${\mathcal {H}}^{(k)}$ содержит не более $\zeta n^{l}$ копии ${\mathcal {F}}^{(k)}$, то можно удалить $\mu n^{k}$ гиперребра в ${\mathcal {H}}^{(k)}$ сделать это ${\mathcal {F}}^{(k)}$-бесплатно.

Одной из первоначальных причин использования метода регулярности графов было доказательство теоремы Семереди , которая утверждает, что каждое плотное подмножество графа $\mathbb {Z}$ содержит арифметическую прогрессию произвольной длины. Фактически, относительно простым применением леммы об удалении треугольника можно доказать, что каждое плотное подмножество $\mathbb {Z}$ содержит арифметическую прогрессию длины 3.

Метод регулярности гиперграфа и лемма об удалении гиперграфа могут доказать многомерные и кольцевые аналоги плотностной версии теорем Семереди, первоначально доказанной Фюрстенбергом и Кацнельсоном. Фактически этот подход дает первые количественные оценки теорем.

Из этой теоремы грубо следует, что любое плотное подмножество $\mathbb {Z} ^{d}$ содержит любой конечный образец $\mathbb {Z} ^{d}$. Тот случай, когда $d=1$ и шаблон представляет собой арифметическую прогрессию длины, некоторая длина эквивалентна теореме Семереди.

Теорема Фюрстенберга и Кацнельсона.

Источник:

Позволять $T$ быть конечным подмножеством $\mathbb {R} ^{d}$ и пусть $\delta >0$ быть дано. Тогда существует конечное подмножество $C\subset \mathbb {R} ^{d}$ такой, что каждый $Z\subset C$ с $|Z|>\delta |C|$ содержит гомотетическую копию $T$. (т.е. набор форм $z+\lambda T$, для некоторых $z\in \mathbb {R} ^{d}$ и $t\in \mathbb {R}$)

Более того, если $T\subset [-t;t]^{d}$ для некоторых $t\in \mathbb {N}$, то существует $N_{0}\in \mathbb {N}$ такой, что $C=[-N,N]^{d}$ имеет это свойство для всех $N\geq N_{0}$.

Другое возможное обобщение, которое можно доказать с помощью леммы об удалении, — это когда размерности разрешено расти.

Теорема Тенгана, Токусигэ, Рёдля и Шахта

Позволять $A$ быть конечным кольцом. Для каждого $\delta >0$, существует $M_{0}$ такой, что для $M\geq M_{0}$, любое подмножество $Z\subset A^{M}$ с $|Z|>\delta |A^{M}|$ содержит смежный класс изоморфной копии $A$ (как левый $A$-модуль).

Другими словами, существуют некоторые $\mathbf {r} ,\mathbf {u} \in A^{M}$ такой, что $r+\varphi (A)\subset Z$, где $\varphi \colon A\to A^{M}$, $\varphi (a)=a\mathbf {u}$ это инъекция.