Лемма о счете

Леммы о счете, обсуждаемые в этой статье, являются утверждениями комбинаторики и теории графов . Первый извлекает информацию из $\epsilon$-регулярные пары подмножеств вершин графа $G$, чтобы гарантировать закономерности во всем графе; более явно, эти шаблоны соответствуют количеству копий определенного графа. $H$ в $G$. Вторая лемма о подсчете дает аналогичное, но более общее представление о пространстве графонов, в котором скаляр расстояния разреза между двумя графами коррелирует с плотностью гомоморфизма между ними и $H$.

Версия леммы о подсчете для встраивания графа

Всякий раз, когда у нас есть $\epsilon$-регулярная пара подмножеств вершин $U,V$ в графике $G$, мы можем интерпретировать это следующим образом: двудольный граф , $(U,V)$, который имеет плотность $d(U,V)$близок вероятностью к случайному двудольному графу, в котором каждое ребро появляется с $d(U,V)$, с некоторыми $\epsilon$ ошибка.

В ситуации, когда у нас есть несколько кластеров вершин, некоторые пары между этими кластерами $\gamma$-регулярный, мы ожидаем, что количество небольших или локальных шаблонов будет примерно равно количеству таких шаблонов в случайном графе. Этими небольшими шаблонами могут быть, например, количество вложений в графы некоторых $H$ в $G$или, более конкретно, количество копий $H$ в $G$ формируется путем взятия одной вершины из каждого кластера вершин.

Вышеизложенная интуиция работает, однако есть несколько важных условий, которые должны быть удовлетворены, чтобы получить полную формулировку теоремы; например, попарные плотности не менее $\varepsilon$, размеры кластеров не менее $\gamma ^{-1}$ , и $\gamma \leq \varepsilon ^{h}/4h$. Если быть более внимательным к этим деталям, формулировка леммы о подсчете графов будет следующей:

Формулировка теоремы

Если $H$ это граф с вершинами $1,\cdots ,h$ и $m$ края, и $G$ это граф с (не обязательно непересекающимися) подмножествами вершин $W_{1},\cdots ,W_{h}$, такой, что $|W_{i}|\geq \gamma ^{-1}$ для всех $i=1,\ldots ,h$ и для каждого края $(i,j)$ из $H$ пара $(W_{i},W_{j})$ является $\gamma$-регулярный по плотности $d(W_{i},W_{j})>\varepsilon$ и $\gamma \leq \varepsilon ^{h}/4h$, затем $G$ содержит как минимум $2^{-h}\varepsilon ^{m}|W_{1}|\cdot \ldots \cdot |W_{h}|$ много копий $H$ с копией вершины $i$ в $W_{i}$.

Эта теорема является обобщением леммы о счете треугольников, которая утверждает вышеизложенное, но с $H=K_{3}$:

Лемма о счете треугольников

Позволять $G$ быть графиком на $n$ вершины, и пусть $X,Y,Z$ быть подмножествами $V(G)$ которые попарно $\epsilon$-regular и предположим, что плотности ребер $d_{XY},d_{XZ},d_{YZ}$ все по крайней мере $2\epsilon$. Тогда количество троек $(x,y,z)\in X\times Y\times Z$ такой, что $x,y,z$ образовать треугольник в $G$ по крайней мере $$(1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )|X||Y||Z|.$$

Доказательство леммы о счете треугольников:

С $(X,Y)$ является регулярной парой, меньше $\varepsilon |X|$ вершин в $X$ иметь меньше, чем $(d_{XY}-\varepsilon )|Y|$ соседи по $Y$; в противном случае этот набор вершин из $X$ вместе со своими соседями по $Y$ станет свидетелем нарушений $(X,Y)$, противоречие. Интуитивно мы говорим, что не слишком много вершин в $X$ может иметь небольшую степень в $Y$.

По аналогичному рассуждению в паре $(X,Z)$, меньше, чем $\varepsilon |X|$ вершин в $X$ иметь меньше, чем $(d_{XZ}-\varepsilon )|Z|$ соседи по $Z$. Объединив эти два подмножества $X$ и взяв их дополнение, мы получим подмножество $X'\subseteq X$ по крайней мере размером $(1-2\varepsilon )|X|$ такой, что каждая вершина $x\in X'$ имеет по крайней мере $(d_{XY}-\varepsilon )|Y|$ соседи по $Y$ и по крайней мере $(d_{XZ}-\varepsilon )|Z|$ соседи по $Z$.

Мы также знаем, что $d_{XY},d_{XZ}\geq 2\varepsilon$, и это $(Y,Z)$ это $\varepsilon$-обычная пара; следовательно, плотность между окрестностями $x$ в $Y$ и окрестности г. $x$ в $Z$ по крайней мере $(d_{YZ}-\varepsilon )$, потому что по регулярности это $\varepsilon$-близкая к фактической плотности между $Y$ и $Z$.

Подводя итог, по крайней мере для каждого из них $(1-2\varepsilon )|X|$ вершины $x\in X'$, есть по крайней мере $(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )|Y||Z|$ выбор ребер между окрестностями $x$ в $Y$ и окрестности г. $x$ в $Z$. Отсюда мы можем завершить это доказательство.

Идея доказательства леммы о подсчете графов: общее доказательство леммы о подсчете графов расширяет этот аргумент посредством жадной стратегии встраивания; а именно вершины $H$ встраиваются в граф одна за другой, используя условие регулярности, чтобы иметь возможность сохранить достаточно большой набор вершин, в который можно было бы встроить следующую вершину.

Графонная версия леммы о счете

Пространство ${\tilde {\mathcal {W}}}_{0}$ графонов разреза задана структура метрического пространства, где метрикой является расстояние $\delta _{\Box }$. Следующая лемма является важным шагом для доказательства того, что $({\tilde {\mathcal {W}}}_{0},\delta _{\Box })$ — компактное метрическое пространство. Интуитивно это говорит о том, что для графа $F$, плотности гомоморфизма двух графонов относительно этого графа должны быть близки (эта оценка зависит от количества ребер $F$), если графоны близки по расстоянию разреза.

Определение (норма отреза).

Норма сокращения ​ $W:[0,1]^{2}\to \mathbb {R}$ определяется как $\|W\|_{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S\times T}W\right|$, где $S$ и $T$ являются измеримыми множествами.

Определение (расстояние реза).

Расстояние реза определяется как $\delta _{\square }(U,W)=\inf _{\phi }||U-W^{\phi }||_{\square }$, где $W^{\phi }(x,y)$ представляет $W(\phi (x),\phi (y))$ для сохраняющей меру биекции $\phi$.

Лемма о счете графонов

Для графонов $W,U$ и график $F$, у нас есть $|t(F,W)-t(F,U)|\leq |E(F)|\delta _{\square }(W,U)$, где $|E(F)|$ обозначает количество ребер графа $F$.

Доказательство леммы о счете графонов:

Достаточно доказать $$|t(F,W)-t(F,U)|\leq |E(F)|\|W-U\|_{\square }.$$Действительно, учитывая вышеизложенное, правая часть выражения имеет множитель $\|W-U^{\phi }\|_{\Box }$ вместо $\|W-U\|_{\Box }$и взяв нижнюю грань по всем сохраняющим меру биекциям $\phi$, мы получаем желаемый результат.

Шаг 1: Реформулировка. Мы доказываем переформулировку нормы сечения , которая по определению является левой частью следующего равенства. Верхняя грань в правой части берется среди измеримых функций $u$ и $v$: $$\sup _{S,T\subseteq [0,1]}\left|\int _{S\times T}W\right|=\sup _{u,v:[0,1]\rightarrow [0,1]}\left|\int _{[0,1]^{2}}W(x,y)u(x)v(y)dxdy\right|.$$

Вот причина, по которой вышеизложенное остается в силе: приняв $u=\mathbb {1} _{S}$ и $u=\mathbb {1} _{T}$, отметим, что левая часть меньше или равна правой. Правая часть меньше или равна левой в силу билинейности подынтегрального выражения в $u,v$, а также тем, что экстремумы достигаются при $u,v$ принимая значения в $0$ или $1$.

Шаг 2: Доказательство $F=K_{3}$. В случае, если $F=K_{3}$, мы наблюдаем, что

$${\begin{aligned}t(K_{3},W)-t(K_{3},U)&=\int _{[0,1]^{3}}((W(x,y)W(x,z)W(y,z)-U(x,y)U(x,z)U(y,z))dxdydz\\&=\int _{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\\&\qquad +\int _{[0,1]^{3}}U(x,y)(W-U)(x,z)W(y,z)dxdydz\\&\qquad +\int _{[0,1]^{3}}U(x,y)U(x,z)(W-U)(y,z)dxdydz.\end{aligned}}$$

К шагу 1 мы имеем это для фиксированного $z$ что

$\left|\int _{[0,1]^{2}}(W-U)(x,y)W(x,z)W(y,z)dxdy\right|\leq \|W-U\|_{\square }$

Поэтому при интегрировании по всем $z\in [0,1]$ мы поняли это

$\left|\int _{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\right|\leq \|W-U\|_{\square }$

Используя эту оценку для каждого из трех слагаемых, мы получаем, что вся сумма ограничена $3\|W-U\|_{\square }$. Шаг 3: Общий случай. Для общего графика $F$, для удобства нам понадобится следующая лемма:

Лемма.

Имеет место следующее выражение: $$a_{1}a_{2}\cdots a_{n}-b_{1}b_{2}\cdots b_{n}=(a_{1}-b_{1})a_{2}\cdots a_{n}+b_{1}(a_{2}-b_{2})\cdots a_{n}+\cdots b_{1}b_{2}\cdots (a_{n}-b_{n}).$$

Приведенная выше лемма следует из непосредственного разложения правой части. Тогда по неравенству нормы треугольника имеем следующее $${\begin{aligned}\left|t(F,W)-t(F,U)\right|&=\left|\int \left(\prod _{u_{i}v_{i}\in E(F)}W(u_{i},v_{i})-\prod _{u_{i}v_{i}\in E(F)}U(u_{i},v_{i})\right)\prod _{v\in V}dv\right|\\&\leq \sum _{i=1}^{|E(F)|}\left|\int \left(\ \prod _{j=1}^{i-1}U(u_{j},v_{j})(W(u_{i},v_{i})-U(u_{i},v_{i}))\prod _{k=i+1}^{|E(F)|}W(u_{k},v_{k})\right)\prod _{v\in V}dv\right|.\end{aligned}}$$

Здесь каждый абсолютный член суммы ограничен нормой сечения $\|W-U\|_{\square }$ если мы зафиксируем все переменные, кроме $u_{i}$ и $v_{i}$ для каждого $i$-th термин, в целом подразумевающий, что $|t(F,W)-t(F,U)|\leq |E(F)|\ \delta _{\square }(W,U)$. Это завершает доказательство.

См. также

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