Lemat o liczeniu

Lematami o liczeniu, o których mowa w tym artykule, są zdania z kombinatoryki i teorii grafów . Pierwszy z nich wydobywa informacje z ${\ displaystyle$ par podzbiorów wierzchołków na grafie , aby zagwarantować wzorce na całym grafie; $\ epsilon }$ dokładniej, wzorce te odpowiadają liczbie kopii pewnego wykresu $H}$ sol ${\ displaystyle$ . Drugi lemat o liczeniu zapewnia podobne, ale bardziej ogólne pojęcie o przestrzeni grafonów, w którym skalar odległości cięcia między dwoma wykresami jest skorelowany z gęstością homomorfizmu między nimi a ${\ displaystyle H}$ .

Wersja lematu o liczeniu z osadzeniem wykresu

Ilekroć mamy $ϵ$ parę podzbiorów wierzchołków na grafie $,$ następujący sposób: wykres dwudzielny . $\ epsilon}$ , ${\ Displaystyle (U, V)}$$bycia$ jest losowym wykresem dwudzielnym , w którym każda krawędź pojawia się z prawdopodobieństwo , $Displaystyle d (U, V)}$ pewnym błędem. re $\$

W ustawieniu, w którym mamy kilka skupisk wierzchołków, przy czym niektóre pary między tymi skupieniami są regularne, spodziewalibyśmy się, że liczba małych lub lokalnych wzorców będzie w przybliżeniu równa liczbie takich ${\ displaystyle \ gamma}$ wzory na losowym wykresie. Te małe wzorce mogą być $H}$ przykład liczbą osadzonych wykresów niektórych $w$$G}$ dokładniej $liczbą$ kopii w sol $displaystyle$ utworzone przez pobranie jednego wierzchołka w każdym klastrze wierzchołków.

Powyższa intuicja działa, ale jest kilka ważnych warunków, które muszą być spełnione, aby mieć pełne sformułowanie twierdzenia; na przykład gęstości parami wynoszą co najmniej $\$ rozmiary klastrów wynoszą co najmniej $Displaystyle \ gamma ^ {- 1}}$ i ${\ displaystyle \ \ gamma \leq \varepsilon ^{h}/4h}$ . Będąc bardziej uważnym na te szczegóły, stwierdzenie lematu o liczeniu grafów jest następujące:

Stwierdzenie twierdzenia

Jeśli jest wykresem z wierzchołkami ${\ Displaystyle 1, \ cdots, h}$$m}$ jest wykresem z (niekoniecznie) $m$$displaystyle$ rozłączne) podzbiory wierzchołków ${\ Displaystyle W_ {1}, \ cdots, W_ {h}}$ , że ${\ Displaystyle | W_ {i} | \ geq \ gamma ^ {- 1}}$ dla wszystkich ${\ Displaystyle i = 1, \ ldots, h}$ i dla każdej krawędzi ${\ Displaystyle (i, j)}$ z ${\ Displaystyle H}$ para ${\ Displaystyle (W_ {i}, W_ {j})}$ jest ${\ Displaystyle \ gamma }$ -regularny o gęstości ${\ Displaystyle d (W_ {i}, W_ {j})> \ varepsilon}$ i $h} / 4h}$${\ Displaystyle \ gamma \ leq \ varepsilon ^$$zawiera$ , to co najmniej ${\ Displaystyle 2 ^ {-h} \ varepsilon ^ {m} | W_ {1} | \ cdot \ ldots \ cdot | W_ {h} |} wiele kopii H. {\ Displaystyle H$ } $kopią$ wierzchołka ${ \ displaystyle i}$ w ${\ displaystyle W_ {i}}$ .

To twierdzenie jest uogólnieniem lematu o liczeniu trójkątów, który stwierdza powyższe, ale z : ${\ Displaystyle H = K_ {3}$ }

Lemat o liczeniu trójkątów

Niech $będzie$ wykresem na $V ($$.$ niech $) {$ podzbiorami które są parami $-regularne$$epsilon$ załóżmy krawędzi są co najmniej ${\ Displaystyle 2 \ epsilon}$ . Wtedy liczba trójek ${\ Displaystyle (x, y, z) \ w X \ razy Y \ razy Z}$ taka, że ${\ Displaystyle x, y, z}$$co$ trójkąt w najmniej

$${\ Displaystyle (1-2 \ epsilon) (d_ {XY} - \ epsilon) (d_ {XZ} - \ epsilon) (d_ {YZ} - \ epsilon) | X || Y|| Z |.}$$

Dowód lematu o liczeniu trójkątów:

Ponieważ ${\ Displaystyle (X, Y)}$ to zwykła para, mniejsza niż ${\ Displaystyle \ varepsilon | X|}$ wierzchołków w ${\ Displaystyle X}$ ma mniej niż ${\ Displaystyle (d_ {XY} - \ varepsilon) | Y |}$ sąsiedzi w ${\ Displaystyle Y}$ ; $przeciwnym$ wierzchołków z wraz z sąsiadami $świadkiem$ byłby $nieregularności$ Intuicyjnie mówimy, że niezbyt wiele wierzchołków w $może$ mieć $mały$ w

Przez analogiczny argument w parze ${\ Displaystyle (X, Z)}$ , mniej niż ${\ Displaystyle \ varepsilon | X|}$ wierzchołków w ${\ Displaystyle X}$ ma mniej niż ${\ Displaystyle (d_ {XZ} - \ varepsilon) | Z |}$ sąsiedzi w ${\ Displaystyle Z}$ . $subseteq X$ te dwa podzbiory i biorąc pod uwagę ich dopełnienie, otrzymujemy podzbiór o rozmiarze co najmniej ${\ Displaystyle (1-2 \ varepsilon) | X|}$${ \$ taki, że każdy wierzchołek ma co najmniej ${\ Displaystyle (d_ {XY} - \ varepsilon) | Y|}$${\ Displaystyle x \ in X '$ sąsiedzi w ${\ Displaystyle Y}$ i przynajmniej ${\ Displaystyle (d_ {XZ} - \ varepsilon) | Z |}$ sąsiedzi w ${\ Displaystyle Z}$ .

Wiemy również, że ${\ Displaystyle d_ {XY}, d_ {XZ} \ geq 2 \ varepsilon}$ i że ( $\ Displaystyle (Y, Z)}$ ε ${\ Displaystyle \ varepsilon}$ zwykła para; ${$ gęstość między $w$ sąsiedztwem $w$$jest$ co $ε$ - , ponieważ z regularności jest ${\$ rzeczywistej gęstości między $displaystyle Y}$ a ${\ displaystyle Z}$ .

Podsumowując, dla każdego z nich co najmniej ${\ Displaystyle (1-2 \ varepsilon) | X |}$ wierzchołki ${\ Displaystyle x \ w X '}$ , jest co najmniej ${\ Displaystyle (d_ {XY} - \ epsilon) (d_ {XZ} - \ epsilon) (d_ {YZ} - \ epsilon) | Y | | Z |} wybory krawędzi między sąsiedztwem$ x $\ displaystyle x}$ w $i$ sąsiedztwo w $displaystyle$$}$ . Stąd możemy zakończyć ten dowód.

Idea dowodu lematu o liczeniu grafów: Ogólny dowód lematu o liczeniu grafów rozszerza ten argument poprzez zachłanną strategię osadzania; mianowicie wierzchołki $grafie jeden po drugim, przy$ warunku regularności, aby móc zachować wystarczająco duży zestaw wierzchołków, w których moglibyśmy osadzić następny wierzchołek.

Grafonowa wersja lematu o liczeniu

Przestrzeń grafonów ma strukturę przestrzeni metrycznej, w której metryką jest odległość cięcia δ $delta _ {\ Pudełko }}$$\$ . $jest$ ważnym krokiem aby zwarta przestrzeń metryczna. Intuicyjnie mówi się, że dla wykresu gęstości homomorfizmu dwóch grafonów w odniesieniu do tego wykresu muszą być bliskie (to ograniczenie zależy od liczby krawędzi ) $,$ jeśli grafony są ${\ displaystyle F$ blisko pod względem odległości cięcia.

Definicja (norma cięcia).

Norma cięcia W ${\ Displaystyle W: [0,1] ^ {2} \ do \ mathbb {R}}$ zdefiniowana jako ${\ Displaystyle \ | W \ | _ {\ kwadrat} = \ sup _ {S, T \ subseteq [0,1]} \ lewo | \ int _ {S \ razy T} W \ prawo |}$ gdzie ${ \displaystyle S}$$zbiorami$ są mierzalnymi .

Definicja (odległość cięcia).

Odległość cięcia jest zdefiniowana jako ${\ Displaystyle \ delta _ {\ kwadrat} (U, W) = \ inf _ {\ phi} || UW ^ {\ phi} || _ {\ kwadrat}},$ gdzie ${ \ Displaystyle W ^ {\ phi} (x, y)}$ reprezentuje ${\ Displaystyle W (\ phi (x), \ phi (y))}$ dla zachowania miary bijekcja ${\ Displaystyle \ phi}$ .

Lemat o liczeniu grafonów

$wykresu$$_$ grafonów i _ $_$ _ ${\ Displaystyle | E (F) |}$ oznacza liczbę krawędzi wykresu ${\ displaystyle F}$ .

Dowód lematu o liczeniu grafonów:

Wystarczy udowodnić

$${\ Displaystyle | t (F, W) -t (F, U) |\ równoważnik | E (F) |\|WU \ | _ {\ kwadrat}.}$$

Rzeczywiście, biorąc pod uwagę powyższe, z wyrażeniem po prawej stronie mającym czynnik $\ Displaystyle \|WU \|_ {\ Box}}$ W $Box}}$${$ i biorąc infimum wszystkich bijekcji zachowujących miarę otrzymujemy pożądany wynik.

Krok 1: Reformulacja. Udowodnimy przeformułowanie normy cięcia , która z definicji jest lewą stroną następującej równości. Supremum po prawej stronie jest zaliczane do mierzalnych funkcji ${\ displaystyle u}$ i ${\ displaystyle v}$ :

$${\ Displaystyle \ sup _ {S, T \ subseteq [0,1]} \ lewo | \ int _ {S \ razy T} W \ prawo | = \ sup _ {u, v: [0,1] \ rightarrow [0,1]}\lewo|\int _{[0,1]^{2}}W(x,y)u(x)v(y)dxdy\prawo|.}$$

Oto powód, dla którego powyższe się utrzymuje: biorąc ${\ Displaystyle u = \ mathbb {1} _ {S}}$ i ${\ Displaystyle u = \ mathbb {1} _ {T}}$ , zauważamy, że lewa strona jest mniejsza lub równa prawej stronie. Prawa strona jest mniejsza lub równa lewej stronie przez dwuliniowość całki w , $fakt$ że ekstrema są osiągane dla ${\ displaystyle u, v }$ przyjmując wartości w ${\ displaystyle 0}$ lub ${\ displaystyle 1}$ .

Krok 2: Dowód dla ${\ Displaystyle F = K_ {3}}$ . W przypadku, gdy obserwujemy to ${\ displaystyle F = K_ {3}}$

$${\ Displaystyle {\ rozpocząć {wyrównane} 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}}(WU)(x,y)W(x,z)W(y,z)dxdydz\\ &\qquad +\int _{[0,1]^{3}}U(x,y)(WU)(x,z)W(y,z)dxdydz\\&\qquad +\int _{[ 0,1]^{3}}U(x,y)U(x,z)(WU)(y,z)dxdydz.\end{wyrównane}}}$$

W kroku 1 mamy to dla $tego$

${\ Displaystyle \ lewo | \ int _ {[0,1] ^ {2}} (WU) (x, y) W (x, z) W (y, z) dxdy \ prawo |\równik \|WU\|_{\kwadrat }}$

Dlatego podczas całkowania po wszystkim otrzymujemy, że ${\ Displaystyle z \ in [0,1]}$

${\ Displaystyle \ lewo | \ int _ {[0,1] ^ {3}} (WU) (x, y) W (x, z) W (y, z) dxdydz \ prawo |\równik \|WU\|_{\kwadrat }}$

Używając tego ograniczenia na każdym z trzech sum, otrzymujemy, że cała suma jest ograniczona przez ${\ Displaystyle 3 \| WU \ | _ {\ kwadrat}}$ . Krok 3: Ogólny przypadek. Aby uzyskać ogólny wykres , potrzebujemy następującego lematu, aby wszystko było wygodniejsze: ${\ displaystyle F}$

Lemat.

Zachodzi następujące wyrażenie:

$${\ Displaystyle 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}) .}$$

Powyższy lemat wynika z prostego rozwinięcia prawej strony. Następnie, na podstawie nierówności trójkąta normy, mamy co następuje

$${\ Displaystyle {\ rozpocząć {wyrównane} \ lewo | t (F, W) -t (F, U) \ prawo | & = \ lewo | \ int \ lewo (\ 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|.\ koniec {wyrównany}}}$$

Tutaj każdy termin wartości bezwzględnej w sumie jest ograniczony przez normę cięcia ${\ Displaystyle \ | WU \ | _ {\ kwadrat}},$ jeśli naprawimy wszystkie zmienne oprócz ${\ displaystyle u_ { ja}}$ i $v_ {i}}$$displaystyle$ dla każdego terminu, co w sumie sugeruje, że ${\ Displaystyle | t (F, W) -t (F, U) |\ równoważnik | E (F) |\ \ delta _ {\ kwadrat} (W, U)}$ . To kończy dowód.

Zobacz też

• Lemat usuwania wykresów