Hispanopedia Wiki
Articulo de referencia

lema de conteo

Los lemas de conteo que se discuten en este artículo son enunciados en combinatoria y teoría de grafos . El primero extrae información de ϵ {\displaystyle \epsilon } -Pares regu...

Hispanopedia WikiContenido en espanolLectura gratuita

Los lemas de conteo que se discuten en este artículo son enunciados en combinatoria y teoría de grafos . El primero extrae información deϵ{\displaystyle \epsilon }-Pares regulares de subconjuntos de vértices en un grafoGRAMO{\displaystyle G}, para garantizar patrones en todo el grafo; más explícitamente, estos patrones corresponden al recuento de copias de un determinado grafo.H{\displaystyle H}enGRAMO{\displaystyle G}. El segundo lema de conteo proporciona una noción similar pero más general sobre el espacio de grafones, en la que un escalar de la distancia de corte entre dos grafos está correlacionado con la densidad de homomorfismos entre ellos yH{\displaystyle H}.

Versión de incrustación de grafos del lema de conteo

Siempre que tengamos unϵ{\displaystyle \epsilon }-par regular de subconjuntos de vérticesU,V{\displaystyle U,V}en un gráficoGRAMO{\displaystyle G}, podemos interpretar esto de la siguiente manera: el grafo bipartito ,(U,V){\displaystyle (U,V)}, que tiene densidadd(U,V){\displaystyle d(U,V)}, se aproxima a ser un grafo bipartito aleatorio en el que cada arista aparece con probabilidadd(U,V){\displaystyle d(U,V)}, con algunosϵ{\displaystyle \epsilon }error.

En un entorno donde tenemos varios grupos de vértices, algunos de los pares entre estos grupos sonγ{\displaystyle \gamma }-regular, esperaríamos que el recuento de patrones pequeños o locales fuera aproximadamente igual al recuento de tales patrones en un grafo aleatorio. Estos patrones pequeños pueden ser, por ejemplo, el número de incrustaciones de grafos de algúnH{\displaystyle H}enGRAMO{\displaystyle G}, o más específicamente, el número de copias deH{\displaystyle H}enGRAMO{\displaystyle G}formado tomando un vértice en cada grupo de vértices.

La intuición anterior funciona, sin embargo, hay varias condiciones importantes que deben cumplirse para tener una formulación completa del teorema; por ejemplo, las densidades por pares son al menosε{\displaystyle \varepsilon }, los tamaños de los clústeres son al menosγ−1{\displaystyle \gamma ^{-1}}, yγ≤εh/4h{\displaystyle \gamma \leq \varepsilon ^{h}/4h}Siendo más cuidadosos con estos detalles, el enunciado del lema de conteo de grafos es el siguiente:

Enunciado del teorema

SiH{\displaystyle H}es un grafo con vértices1,⋯,h{\displaystyle 1,\cdots ,h}ymetro{\displaystyle m}bordes yGRAMO{\displaystyle G}es un grafo con subconjuntos de vértices (no necesariamente disjuntos)W1,⋯,Wh{\displaystyle W_{1},\cdots,W_{h}}, de tal manera que|Wi|≥γ−1{\displaystyle |W_{i}|\geq \gamma ^{-1}}a pesar dei=1,…,h{\displaystyle i=1,\ldots ,h}y por cada borde(i,j){\displaystyle (i,j)}deH{\displaystyle H}la pareja(Wi,Wj){\displaystyle (W_{i},W_{j})}esγ{\displaystyle \gamma }-regular con densidadd(Wi,Wj)>ε{\displaystyle d(W_{i},W_{j})>\varepsilon }yγ≤εh/4h{\displaystyle \gamma \leq \varepsilon ^{h}/4h}, entoncesGRAMO{\displaystyle G}contiene al menos2−hεmetro|W1|⋅…⋅|Wh|{\displaystyle 2^{-h}\varepsilon ^{m}|W_{1}|\cdot \ldots \cdot |W_{h}|}muchas copias deH{\displaystyle H}con la copia del vérticei{\displaystyle i}enWi{\displaystyle W_{i}}.

Este teorema es una generalización del lema de conteo de triángulos, que establece lo anterior pero conH=K3{\displaystyle H=K_{3}}:

Lema del conteo de triángulos

DejarGRAMO{\displaystyle G}ser un gráfico ennorte{\displaystyle n}vértices, y dejeincógnita,Y,Z{\displaystyle X,Y,Z}ser subconjuntos deV(GRAMO){\displaystyle V(G)}que son paresϵ{\displaystyle \epsilon }-regular , y supongamos que las densidades de bordedincógnitaY,dincógnitaZ,dYZ{\displaystyle d_{XY},d_{XZ},d_{YZ}}son todos al menos2ϵ{\displaystyle 2\epsilon }. Entonces el número de tríos(incógnita,y,z)∈incógnita×Y×Z{\displaystyle (x,y,z)\in X\times Y\times Z}de tal manera queincógnita,y,z{\displaystyle x,y,z}formen un triángulo enGRAMO{\displaystyle G}es al menos(1−2ϵ)(dincógnitaY−ϵ)(dincógnitaZ−ϵ)(dYZ−ϵ)|incógnita||Y||Z|.{\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )|X||Y||Z|.}

Demostración del lema de conteo de triángulos:

Desde(incógnita,Y){\displaystyle (X,Y)}es un par regular, menos deε|incógnita|{\displaystyle \varepsilon |X|}de los vértices enincógnita{\displaystyle X}tienen menos que(dincógnitaY−ε)|Y|{\displaystyle (d_{XY}-\varepsilon )|Y|}vecinos enY{\displaystyle Y}; de lo contrario, este conjunto de vértices deincógnita{\displaystyle X}junto con sus vecinos enY{\displaystyle Y}presenciaría irregularidades de(incógnita,Y){\displaystyle (X,Y)}, una contradicción. Intuitivamente, estamos diciendo que no hay demasiados vértices enincógnita{\displaystyle X}puede tener un pequeño grado enY{\displaystyle Y}.

Mediante un argumento análogo en el par(incógnita,Z){\displaystyle (X,Z)}, menos deε|incógnita|{\displaystyle \varepsilon |X|}de los vértices enincógnita{\displaystyle X}tienen menos que(dincógnitaZ−ε)|Z|{\displaystyle (d_{XZ}-\varepsilon )|Z|}vecinos enZ{\displaystyle Z}. Combinando estos dos subconjuntos deincógnita{\displaystyle X}y tomando su complemento, obtenemos un subconjuntoincógnita′⊆incógnita{\displaystyle X'\subseteq X}de tamaño al menos(1−2ε)|incógnita|{\displaystyle (1-2\varepsilon )|X|}de tal manera que cada vérticeincógnita∈incógnita′{\displaystyle x\in X'}tiene al menos(dincógnitaY−ε)|Y|{\displaystyle (d_{XY}-\varepsilon )|Y|}vecinos enY{\displaystyle Y}y al menos(dincógnitaZ−ε)|Z|{\displaystyle (d_{XZ}-\varepsilon )|Z|}vecinos enZ{\displaystyle Z}.

También sabemos quedincógnitaY,dincógnitaZ≥2ε{\displaystyle d_{XY},d_{XZ}\geq 2\varepsilon }y que(Y,Z){\displaystyle (Y,Z)}es unε{\displaystyle \varepsilon }-par regular; por lo tanto, la densidad entre el vecindario deincógnita{\displaystyle x}enY{\displaystyle Y}y el vecindario deincógnita{\displaystyle x}enZ{\displaystyle Z}es al menos(dYZ−ε){\displaystyle (d_{YZ}-\varepsilon )}, porque por regularidad esε{\displaystyle \varepsilon }-cerca de la densidad real entreY{\displaystyle Y}yZ{\displaystyle Z}.

En resumen, para cada uno de estos al menos(1−2ε)|incógnita|{\displaystyle (1-2\varepsilon )|X|}vérticesincógnita∈incógnita′{\displaystyle x\in X'}, hay al menos(dincógnitaY−ϵ)(dincógnitaZ−ϵ)(dYZ−ϵ)|Y||Z|{\displaystyle (d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )|Y||Z|}elecciones de bordes entre el vecindario deincógnita{\displaystyle x}enY{\displaystyle Y}y el vecindario deincógnita{\displaystyle x}enZ{\displaystyle Z}A partir de ahí podemos concluir esta demostración.

Idea de demostración del lema de conteo de grafos: La demostración general del lema de conteo de grafos extiende este argumento a través de una estrategia de incrustación voraz ; es decir, vértices deH{\displaystyle H}se incrustan en el grafo uno por uno, utilizando la condición de regularidad para poder mantener un conjunto suficientemente grande de vértices en el que podamos incrustar el siguiente vértice. [ 1 ]

Versión grafónica del lema de conteo

El espacioW~0{\displaystyle {\tilde {\mathcal {W}}}_{0}}A los grafones se les da la estructura de un espacio métrico donde la métrica es la distancia de corte.δ◻{\displaystyle \delta _{\Box }}El siguiente lema es un paso importante para demostrar que(W~0,δ◻){\displaystyle ({\tilde {\mathcal {W}}}_{0},\delta _{\Box })}es un espacio métrico compacto. Intuitivamente, dice que para un grafoF{\displaystyle F}Las densidades de homomorfismo de dos grafones con respecto a este grafo deben ser cercanas (este límite depende del número de aristas).F{\displaystyle F}) si los grafones están cerca en términos de distancia de corte.

Definición (norma de corte).

La norma de corte deW:[0,1]2→R{\displaystyle W:[0,1]^{2}\to \mathbb {R} }se define como‖W‖◻=sorberS,T⊆[0,1]|∫S×TW|{\displaystyle \|W\|_{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S\times T}W\right|}, dóndeS{\displaystyle S}yT{\displaystyle T}son conjuntos medibles.

Definición (distancia de corte).

La distancia de corte se define comoδ◻(U,W)=infϕ||U−Wϕ||◻{\displaystyle \delta _{\square }(U,W)=\inf _{\phi }||U-W^{\phi }||_{\square }}, dóndeWϕ(incógnita,y){\displaystyle W^{\phi }(x,y)}representaW(ϕ(incógnita),ϕ(y)){\displaystyle W(\phi (x),\phi (y))}para una biyección que preserva la medidaϕ{\displaystyle \phi }.

Lema de conteo de grafones

Para grafonesW,U{\displaystyle W,U}y gráficoF{\displaystyle F}, tenemos|t(F,W)−t(F,U)|≤|mi(F)|δ◻(W,U){\displaystyle |t(F,W)-t(F,U)|\leq |E(F)|\delta _{\square }(W,U)}, dónde|mi(F)|{\displaystyle |E(F)|}denota el número de aristas del grafoF{\displaystyle F}.

Demostración del lema de conteo de grafones:

Basta con demostrarlo|t(F,W)−t(F,U)|≤|mi(F)|‖W−U‖◻.{\displaystyle |t(F,W)-t(F,U)|\leq |E(F)|\|W-U\|_{\square }.}En efecto, al considerar lo anterior, con la expresión del lado derecho teniendo un factor‖W−Uϕ‖◻{\displaystyle \|W-U^{\phi }\|_{\Box }}en lugar de‖W−U‖◻{\displaystyle \|W-U\|_{\Box }}y tomando el ínfimo de todas las biyecciones que preservan la medidaϕ{\displaystyle \phi }, obtenemos el resultado deseado.

Paso 1: Reformulación. Demostramos una reformulación de la norma de corte , que por definición es el lado izquierdo de la siguiente igualdad. El supremo en el lado derecho se toma entre funciones medibles.tú{\displaystyle u}yv{\displaystyle v}:sorberS,T⊆[0,1]|∫S×TW|=sorbertú,v:[0,1]→[0,1]|∫[0,1]2W(incógnita,y)tú(incógnita)v(y)dincógnitady|.{\displaystyle \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|.}

He aquí la razón por la que lo anterior se cumple: Al tomartú=1S{\displaystyle u=\mathbb {1} _{S}}ytú=1T{\displaystyle u=\mathbb {1} _{T}}, observamos que el lado izquierdo es menor o igual que el lado derecho. El lado derecho es menor o igual que el lado izquierdo por la bilinealidad del integrando entú,v{\displaystyle u,v}y por el hecho de que los extremos se alcanzan paratú,v{\displaystyle u,v}tomando valores en0{\displaystyle 0}o1{\displaystyle 1}.

Paso 2: Prueba deF=K3{\displaystyle F=K_{3}}. En el caso de queF=K3{\displaystyle F=K_{3}}, observamos que

t(K3,W)−t(K3,U)=∫[0,1]3((W(incógnita,y)W(incógnita,z)W(y,z)−U(incógnita,y)U(incógnita,z)U(y,z))dincógnitadydz=∫[0,1]3(W−U)(incógnita,y)W(incógnita,z)W(y,z)dincógnitadydz+∫[0,1]3U(incógnita,y)(W−U)(incógnita,z)W(y,z)dincógnitadydz+∫[0,1]3U(incógnita,y)U(incógnita,z)(W−U)(y,z)dincógnitadydz.{\displaystyle {\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}}}

En el paso 1, tenemos que para un fijoz{\displaystyle z}eso

|∫[0,1]2(W−U)(incógnita,y)W(incógnita,z)W(y,z)dincógnitady|≤‖W−U‖◻{\displaystyle \left|\int _{[0,1]^{2}}(W-U)(x,y)W(x,z)W(y,z)dxdy\right|\leq \|W-U\|_{\square }}

Por lo tanto, al integrar sobre todosz∈[0,1]{\displaystyle z\in [0,1]} lo entendemos

|∫[0,1]3(W−U)(incógnita,y)W(incógnita,z)W(y,z)dincógnitadydz|≤‖W−U‖◻{\displaystyle \left|\int _{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\right|\leq \|W-U\|_{\square }}

Utilizando esta cota en cada uno de los tres sumandos, obtenemos que la suma total está acotada por3‖W−U‖◻{\displaystyle 3\|W-U\|_{\square }}Paso 3: Caso general. Para un gráfico generalF{\displaystyle F}Necesitamos el siguiente lema para que todo sea más conveniente:

Lema.

Se cumple la siguiente expresión:a1a2⋯anorte−b1b2⋯bnorte=(a1−b1)a2⋯anorte+b1(a2−b2)⋯anorte+⋯b1b2⋯(anorte−bnorte).{\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}).}

El lema anterior se deduce de una expansión directa del lado derecho. Entonces, por la desigualdad triangular de la norma, tenemos lo siguiente:|t(F,W)−t(F,U)|=|∫(∏túivi∈mi(F)W(túi,vi)−∏túivi∈mi(F)U(túi,vi))∏v∈Vdv|≤∑i=1|mi(F)||∫( ∏j=1i−1U(túj,vj)(W(túi,vi)−U(túi,vi))∏k=i+1|mi(F)|W(túk,vk))∏v∈Vdv|.{\displaystyle {\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}}}

Aquí, cada término de valor absoluto en la suma está acotado por la norma de corte.‖W−U‖◻{\displaystyle \|W-U\|_{\square }}si fijamos todas las variables exceptotúi{\displaystyle u_{i}}yvi{\displaystyle v_{i}}para cadai{\displaystyle i}-ésimo término, lo que implica en conjunto que|t(F,W)−t(F,U)|≤|mi(F)| δ◻(W,U){\displaystyle |t(F,W)-t(F,U)|\leq |E(F)|\ \delta _{\square }(W,U)}Con esto finaliza la demostración.

Véase también

Referencias

  1. ↑ Conlon, Fox, David, Jacob. "Lemas de eliminación de grafos" (PDF) . Página web de David Conlon . Archivado (PDF) del original el 1 de octubre de 2013.{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )