Método de contenedor

Método en combinatoria

El método de contenedores (hipergráficos) es una herramienta poderosa que puede ayudar a caracterizar la estructura típica y/o responder preguntas extremales sobre familias de objetos discretos con un conjunto prescrito de restricciones locales. Tales preguntas surgen naturalmente en la teoría de grafos extremales , la combinatoria aditiva , la geometría discreta , la teoría de codificación y la teoría de Ramsey ; incluyen algunos de los problemas más clásicos en los campos asociados.

Estos problemas pueden expresarse como preguntas de la siguiente forma: dado un hipergrafo H sobre un conjunto finito de vértices V con un conjunto de aristas E (es decir, una colección de subconjuntos de V con algunas restricciones de tamaño), ¿qué podemos decir acerca de los conjuntos independientes de H (es decir, aquellos subconjuntos de V que no contienen ningún elemento de E )? El lema del contenedor del hipergrafo proporciona un método para abordar tales preguntas.

Historia

Uno de los problemas fundamentales de la teoría de grafos extremales, que data del trabajo de Mantel en 1907 y de Turán de la década de 1940, busca caracterizar aquellos grafos que no contienen una copia de algún H prohibido fijo como subgrafo. En un dominio diferente, una de las preguntas motivadoras en la combinatoria aditiva es entender cuán grande puede ser un conjunto de números enteros sin contener una progresión aritmética de k términos , con límites superiores para este tamaño dados por Roth ( ) y Szemerédi ( k general ). ${\displaystyle k=3}$

El método de contenedores (en grafos) fue inicialmente desarrollado por Kleitman y Winston en 1980, quienes limitaron el número de redes ^[1] y grafos sin 4-ciclos. ^[2] Los lemas de estilo contenedor fueron desarrollados independientemente por múltiples matemáticos en diferentes contextos, incluyendo notablemente a Sapozhenko, quien inicialmente utilizó este enfoque en 2002-2003 para enumerar conjuntos independientes en grafos regulares , ^[3] conjuntos sin suma en grupos abelianos, ^[4] y estudiar una variedad de otros problemas de enumeración ^[5].

^{Saxton y Thomason [6]} y Balogh, Morris y Samotij ^[7] idearon de forma independiente una generalización de estas ideas a un lema contenedor de hipergrafos en 2015, inspirados por una variedad de trabajos anteriores relacionados.

Idea principal y enunciado informal

Muchos problemas de combinatoria pueden reformularse como preguntas sobre conjuntos independientes en grafos e hipergrafos. Por ejemplo, supongamos que deseamos comprender subconjuntos de números enteros de 1 a n , que denotamos por que carecen de una progresión aritmética de k términos. Estos conjuntos son exactamente los conjuntos independientes en el hipergrafo k -uniforme , donde E es la colección de todas las progresiones aritméticas de k términos en . ${\displaystyle [n]}$ ${\displaystyle H=(\{1,2,\ldots ,n\},E)}$ ${\displaystyle \{1,2,\ldots ,n\}}$

En los casos anteriores (y muchos otros), normalmente se plantean dos clases naturales de problemas sobre un hipergrafo H :

• ¿Cuál es el tamaño de un conjunto independiente máximo en H ? ¿Cómo es la colección de conjuntos independientes de tamaño máximo en H ?
• ¿Cuántos conjuntos independientes tiene H ? ¿Cómo es un conjunto independiente "típico" en H ?

Estos problemas están conectados por una simple observación. Sea el tamaño del conjunto independiente más grande de H y supongamos que tiene conjuntos independientes. Entonces, ${\displaystyle \alpha (H)}$ ${\displaystyle H}$ ${\displaystyle i(H)}$

${\displaystyle 2^{\alpha (H)}\leq i(H)\leq \sum _{r=0}^{\alpha (H)}{|V(H)| \choose r},}$

donde el límite inferior se obtiene tomando todos los subconjuntos de un conjunto máximo independiente. Estos límites están relativamente alejados entre sí a menos que sea muy grande, cerca del número de vértices del hipergrafo. Sin embargo, en muchos hipergrafos que surgen naturalmente en problemas combinatorios, tenemos razones para creer que el límite inferior está más cerca del valor verdadero; por lo tanto, el objetivo principal es mejorar los límites superiores en i(H) . ${\displaystyle \alpha (H)}$

El lema del contenedor hipergráfico proporciona un enfoque poderoso para comprender la estructura y el tamaño de la familia de conjuntos independientes en un hipergrafo. En esencia, el método del contenedor hipergráfico nos permite extraer de un hipergrafo, una colección de contenedores , subconjuntos de vértices que satisfacen las siguientes propiedades:

• No hay demasiados contenedores.
• Cada contenedor no es mucho más grande que el conjunto independiente más grande.
• Cada contenedor tiene pocos bordes.
• Cada conjunto independiente en el hipergrafo está completamente incluido en algún contenedor.

El nombre contenedor alude a esta última condición. Estos contenedores suelen proporcionar un enfoque eficaz para caracterizar la familia de conjuntos independientes (subconjuntos de los contenedores) y para enumerar los conjuntos independientes de un hipergrafo (considerando simplemente todos los subconjuntos posibles de un contenedor).

El lema del contenedor del hipergrafo logra la descomposición del contenedor anterior en dos partes. Construye una función determinista f . Luego, proporciona un algoritmo que extrae de cada conjunto independiente I en el hipergrafo H , una colección relativamente pequeña de vértices , llamada huella digital, con la propiedad de que . Luego, los contenedores son la colección de conjuntos que surgen en el proceso anterior, y el pequeño tamaño de las huellas digitales proporciona un buen control sobre la cantidad de dichos conjuntos de contenedores. ${\displaystyle S\subset I}$ ${\displaystyle S\subset I\subset S\cup f(S)}$ ${\displaystyle S\cup f(S)}$

Algoritmo de contenedor de gráficos

Primero describimos un método para mostrar límites superiores fuertes en el número de conjuntos independientes en un gráfico; esta exposición es una adaptación de una encuesta de Samotij ^[8] sobre el método contenedor de gráficos, originalmente empleado por Kleitman-Winston y Sapozhenko.

Notación

Utilizamos la siguiente notación en la siguiente sección.

• ${\displaystyle G=(V,E)}$es un gráfico sobre vértices, donde el conjunto de vértices está equipado con un ordenamiento (arbitrario) . ${\displaystyle |V|=n}$ ${\displaystyle \{v_{1},\ldots ,v_{n}\}}$
• Sea la colección de conjuntos independientes de G con tamaño . Sea el número de conjuntos independientes de tamaño r . ${\displaystyle \ell (G)}$ ${\displaystyle i(G):=|\ell (G)|}$ ${\displaystyle i(G,r)}$
• El ordenamiento de grado máximo de un subconjunto de vértices es el ordenamiento de los vértices en A por su grado en el subgrafo inducido . ${\displaystyle A\subset V}$ ${\displaystyle G[A]}$

Algoritmo de Kleitman-Winston

El siguiente algoritmo proporciona una pequeña "huella dactilar" para cada conjunto independiente en un gráfico y una función determinista de la huella dactilar para construir un subconjunto no demasiado grande que contenga todo el conjunto independiente.

Fijar el gráfico G , conjunto independiente y entero positivo . ${\displaystyle I\in \ell (G)}$ ${\displaystyle q\leq |I|}$

1. Inicializar : dejar . ${\displaystyle A=V(G),S=\emptyset }$
2. Iterar para : ${\displaystyle s=1,2,\ldots ,q}$
   • Construir el ordenamiento de máximo grado de ${\displaystyle A,\,(v_{1},\ldots v_{|A|})}$
   • Encuentra el índice mínimo tal que (es decir, el vértice en A de mayor grado en el subgrafo inducido G[A] ) ${\displaystyle j_{s}}$ ${\displaystyle v_{j_{s}}\in I}$
   • Sea , donde es el vecindario del vértice . ${\displaystyle S\leftarrow S\cup \{v_{j_{s}}\},\,A\leftarrow A\backslash (\{v_{1},\ldots ,v_{j_{s}}\}\cup N(v_{j_{s}}))}$ ${\displaystyle N(v)}$ ${\displaystyle v}$
3. Genera el vector y el conjunto de vértices . ${\displaystyle (j_{1},\ldots ,j_{q})}$ ${\displaystyle A\cap I}$

Análisis

Por construcción, la salida del algoritmo anterior tiene la propiedad de que , notando que es un subconjunto de vértices que está completamente determinado por y no es una función de . Para enfatizar esto, escribiremos . También observamos que podemos reconstruir el conjunto en el algoritmo anterior solo a partir del vector . ${\displaystyle \{v_{j_{1}},\ldots ,v_{j_{q}}\}\subset I\subset \{v_{j_{1}},\ldots ,v_{j_{q}}\}\cup (A\cap I)}$ ${\displaystyle A\cap I}$ ${\displaystyle \{j_{1},\ldots ,j_{q}\}}$ ${\displaystyle I}$ ${\displaystyle A=A(j_{1},\ldots ,j_{q})}$ ${\displaystyle S=\{v_{j_{1}},\ldots ,v_{j_{q}}\}=S(j_{1},\ldots j_{q})}$ ${\displaystyle (j_{1},\ldots ,j_{q})}$

Esto sugiere que podría ser una buena elección de huella digital y de contenedor . Más precisamente, podemos limitar el número de conjuntos independientes de cierto tamaño como una suma de secuencias de salida. ${\displaystyle S}$ ${\displaystyle S(j_{1},\ldots j_{q})\cup A(j_{1},\ldots ,j_{q})}$ ${\displaystyle G}$ ${\displaystyle r\geq q}$ ${\displaystyle (j_{1},\ldots j_{q})}$

${\displaystyle i(G,r)=\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})],r-q)\leq \sum _{(j_{s})}{A(j_{1},\ldots j_{q}) \choose r-q}}$,

donde podemos sumar para obtener un límite en el número total de conjuntos independientes del gráfico: ${\displaystyle r}$

${\displaystyle i(G)=\sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})])\leq \sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})}2^{|A(j_{1},\ldots j_{q})|}}$.

Al intentar minimizar este límite superior, queremos elegir un valor que equilibre o minimice estos dos términos. Este resultado ilustra el valor de ordenar los vértices por grado máximo (para minimizar ). ${\displaystyle q}$ ${\displaystyle |A(j_{1},\ldots j_{q})|}$

Lemas

Las desigualdades y observaciones anteriores se pueden plantear en un contexto más general, separado de una suma explícita sobre vectores . ${\displaystyle (j_{s})}$

Lema 1: Dado un grafo con y supongamos que los números enteros y reales satisfacen . Supongamos que cada subgrafo inducido en al menos vértices tiene una densidad de aristas de al menos . Entonces, para cada entero , ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle R,\beta \in [0,1]}$ ${\displaystyle R\geq e^{-\beta q}n}$ ${\displaystyle R}$ ${\displaystyle \beta }$ ${\displaystyle r\geq q}$

${\displaystyle i(G,r)\leq {n \choose q}{R \choose r-q}.}$

Lema 2: Sea un grafo sobre vértices y supongamos que se eligen un entero y unos números reales tales que . Si todos los subconjuntos de al menos vértices tienen al menos aristas, entonces existe una colección de subconjuntos de vértices ("huellas dactilares") y una función determinista , de modo que para cada conjunto independiente , existe tal que . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle R,D}$ ${\displaystyle n\leq R+qD}$ ${\displaystyle U}$ ${\displaystyle R}$ ${\displaystyle D|U|/2}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle q}$ ${\displaystyle f\colon {\mathcal {C}}\rightarrow {\mathcal {P}}(V(G))}$ ${\displaystyle I\subset V(G)}$ ${\displaystyle S\in {\mathcal {F}}}$ ${\displaystyle S\subset I\subset f(S)\cup S}$

Lema del contenedor hipergráfico

De manera informal, el lema del contenedor del hipergrafo nos dice que podemos asignar una huella digital pequeña a cada conjunto independiente, de modo que todos los conjuntos independientes con la misma huella digital pertenezcan al mismo conjunto más grande, , el contenedor asociado , que tiene un tamaño acotado a partir del número de vértices del hipergrafo. Además, estas huellas digitales son pequeñas (y, por lo tanto, hay pocos contenedores), y podemos acotar su tamaño de una manera esencialmente óptima utilizando algunas propiedades simples del hipergrafo. ${\displaystyle S\subset I}$ ${\displaystyle C=f(S)}$

Recordamos la siguiente notación asociada al hipergrafo uniforme . ${\displaystyle k}$ ${\displaystyle {\mathcal {H}}}$

• Definir para números enteros positivos , donde . ${\displaystyle \Delta _{l}({\mathcal {H}}):=\max\{d_{H}(A)\mid A\subset V({\mathcal {H}}),|A|=l\}}$ ${\displaystyle 1\leq l\leq k}$ ${\displaystyle d_{\mathcal {H}}(A)=|\{e\in E({\mathcal {H}})\mid A\subset e\}|}$
• Sea la colección de conjuntos independientes de . denotará algún conjunto independiente de este tipo. ${\displaystyle {\mathcal {I}}({\mathcal {H}})}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle I}$

Declaración

Enunciamos la versión de este lema que se encuentra en un trabajo de Balogh, Morris, Samotij y Saxton. ^[9]

Sea un hipergrafo -uniforme y supongamos que para cada y algún , tenemos que . Entonces, existe una colección y una función tales que ${\displaystyle {\mathcal {H}}}$ ${\displaystyle k}$ ${\displaystyle l\in \{1,2,\ldots ,k\}}$ ${\displaystyle b,r\in \mathbb {N} }$ ${\displaystyle \Delta _{l}(H)\leq \left({\frac {b}{|V(H)|}}\right)^{l-1}{\frac {|E(H)|}{r}}}$ ${\displaystyle {\mathcal {C}}\subset {\mathcal {P}}(V(H))}$ ${\displaystyle f\colon {\mathcal {P}}(V(H))\rightarrow {\mathcal {C}}}$

• para cada existe con y . ${\displaystyle I\in {\mathcal {I}}(H)}$ ${\displaystyle S\subset I}$ ${\displaystyle |S|\leq (k-1)b}$ ${\displaystyle I\subset f(S)}$
• ${\displaystyle |C|\leq |V(H)|-\delta r}$para cada y . ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle \delta =2^{-k(k+1)}}$

Ejemplos de aplicaciones

Gráficas regulares

Límite superior del número de conjuntos independientes

Demostraremos que existe una constante absoluta C tal que todo grafo -vértice -regular satisface . ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle i(G)\leq 2^{\left(1+C{\sqrt {\frac {\log d}{d}}}\right){\frac {n}{2}}}}$

Podemos limitar el número de conjuntos independientes de cada tamaño utilizando el límite trivial para . Para , mayor , tomemos Con estos parámetros, el grafo d -regular satisface las condiciones del Lema 1 y, por lo tanto, ${\displaystyle r}$ ${\displaystyle i(G,r)\leq {n \choose r}\leq {n \choose n/10}\leq 2^{0.48n}}$ ${\displaystyle r\leq n/10}$ ${\displaystyle r}$ ${\displaystyle \beta >10/n,q=\lfloor 1/\beta \rfloor ,R={\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}.}$ ${\displaystyle G}$

${\displaystyle i(G,r)\leq {n \choose q}{R \choose r-q}\leq {n \choose q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq \left({\frac {en}{q}}\right)^{q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq (e\beta n)^{\lfloor 1/\beta \rfloor }{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}.}$

Sumando todo se obtiene ${\displaystyle 0\leq r\leq n}$

${\displaystyle i(G)\leq 2^{0.49n}+2^{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}+\lfloor 1/\beta \rfloor \log _{2}(e\beta n)}}$,

que produce el resultado deseado cuando lo conectamos ${\displaystyle \beta ={\sqrt {d\log d}}/n.}$

Conjuntos sin suma

Un conjunto de elementos de un grupo abeliano se denomina de suma libre si no hay ningún conjunto que satisfaga . Demostraremos que hay, como máximo, subconjuntos de suma libre de . ${\displaystyle A}$ ${\displaystyle x,y,z\in A}$ ${\displaystyle x+y=z}$ ${\displaystyle 2^{(1/2+o(1))n}}$ ${\displaystyle [n]:=\{1,2,\ldots ,n\}}$

Esto se desprende de los límites que hemos establecido anteriormente sobre el número de conjuntos independientes en un grafo regular. Para comprobarlo, necesitaremos construir un grafo auxiliar. En primer lugar, observamos que, hasta los términos de orden inferior, podemos limitar nuestro enfoque a conjuntos sin suma con al menos elementos menores que (ya que el número de subconjuntos en el complemento de este es como máximo ). ${\displaystyle n^{2/3}}$ ${\displaystyle n/2}$ ${\displaystyle (n/2)^{n^{2/3}}2^{n/2+1}}$

Dado un subconjunto , definimos un grafo auxiliar con un conjunto de vértices y un conjunto de aristas , y observamos que nuestro grafo auxiliar es regular ya que cada elemento de S es menor que . Entonces, si son los elementos más pequeños del subconjunto , el conjunto es un conjunto independiente en el grafo . Entonces, por nuestro límite anterior, vemos que el número de subconjuntos sin suma de es como máximo ${\displaystyle S\subset \{1,2,\ldots ,\lceil n/2\rceil -1\}}$ ${\displaystyle G_{S}}$ ${\displaystyle [n]}$ ${\displaystyle \{\{x,y\}\mid x+s\equiv y{\pmod {n}}{\text{ for some }}s\in S\cup (-S)\}}$ ${\displaystyle 2|S|}$ ${\displaystyle n/2}$ ${\displaystyle S_{A}}$ ${\displaystyle n^{2/3}}$ ${\displaystyle A\subset [n]}$ ${\displaystyle A\backslash S_{A}}$ ${\displaystyle G_{S_{A}}}$ ${\displaystyle [n]}$

${\displaystyle (n/2)^{n^{2/3}}2^{n/2+}+{n/2 \choose n^{2/3}}2^{(1+O(n^{-1/3}{\sqrt {\log n}})){\frac {n}{2}}}\leq 2^{(1/2+O(n^{-1/3}\log n))n}.}$

Gráficos sin triángulos

Damos una ilustración del uso del lema del contenedor de hipergrafos para responder una pregunta enumerativa al dar un límite superior asintóticamente estricto al número de grafos libres de triángulos con vértices. ^[10] ${\displaystyle n}$

Declaración informal

Dado que los grafos bipartitos no tienen triángulos, el número de grafos sin triángulos con vértices es al menos , que se obtiene enumerando todos los subgrafos posibles del grafo bipartito completo equilibrado . ${\displaystyle n}$ ${\displaystyle 2^{\lfloor n^{2}/4\rfloor }}$ ${\displaystyle K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }}$

Podemos construir un hipergrafo auxiliar 3 -uniforme H con un conjunto de vértices y un conjunto de aristas . Este hipergrafo "codifica" triángulos en el sentido de que la familia de grafos sin triángulos en los vértices es exactamente la colección de conjuntos independientes de este hipergrafo, . ${\displaystyle V(H)=E(K_{n})}$ ${\displaystyle E(H)=\{\{e_{1},e_{2},e_{3}\}\subset E(K_{n})=V(H)\mid e_{1},e_{2},e_{3}{\text{ form a triangle}}\}}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {I}}(H)}$

El hipergrafo anterior tiene una distribución de grados agradable: cada arista de , y por lo tanto el vértice en está contenido en exactamente triángulos y cada par de elementos en está contenido en, como máximo, 1 triángulo. Por lo tanto, al aplicar el lema del contenedor del hipergrafo (de manera iterativa), podemos demostrar que existe una familia de contenedores que contienen cada uno de ellos unos pocos triángulos que contienen todos los grafos sin triángulos/conjuntos independientes del hipergrafo. ${\displaystyle K_{n}}$ ${\displaystyle V(H)}$ ${\displaystyle n-2}$ ${\displaystyle V(H)}$ ${\displaystyle n^{O(n^{3/2})}}$

Límite superior del número de grafos sin triángulos

Primero especializamos el lema contenedor de hipergrafos genéricos en hipergrafos 3-uniformes de la siguiente manera:

Lema: Para cada , existe tal que se cumple lo siguiente. Sea un hipergrafo 3-uniforme con grado medio y supongamos que . Entonces existe una colección de, como máximo, contenedores tales que ${\displaystyle c>0}$ ${\displaystyle \delta >0}$ ${\displaystyle H}$ ${\displaystyle d\geq 1/\delta }$ ${\displaystyle \Delta _{1}(H)\leq cd,\Delta _{2}(H)\leq c{\sqrt {d}}}$ ${\displaystyle {\mathcal {C}}\subset {\mathcal {P}}(V(H))}$ ${\displaystyle |{\mathcal {C}}|\leq {|V(H)| \choose |V(H)|/{\sqrt {d}}}}$

• Para cada , existe ${\displaystyle I\in {\mathcal {I}}(H)}$ ${\displaystyle I\subset C\in {\mathcal {C}}}$
• ${\displaystyle |C|\leq (1-\delta )|V(H)|}$a pesar de ${\displaystyle C\in {\mathcal {C}}}$

Aplicando este lema iterativamente obtendremos el siguiente teorema (como se demuestra a continuación):

Teorema: Para todo , existe tal que se cumple lo siguiente. Para cada entero positivo n , existe una colección de grafos en n vértices con tal que ${\displaystyle \epsilon >0}$ ${\displaystyle C>0}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle |{\mathcal {G}}|\leq n^{Cn^{3/2}}}$

• cada uno tiene menos de triángulos, ${\displaystyle G\in {\mathcal {G}}}$ ${\displaystyle \epsilon n^{3}}$
• Cada grafo libre de triángulos en vértices está contenido en algún . ${\displaystyle n}$ ${\displaystyle G\in {\mathcal {G}}}$

Demostración: Consideremos el hipergrafo definido anteriormente. Como se observó informalmente antes, el hipergrafo satisface para cada . Por lo tanto, podemos aplicar el Lema anterior a con para encontrar alguna colección de subconjuntos de (es decir, grafos en vértices) tales que ${\displaystyle H}$ ${\displaystyle |V(H)|={n \choose 2},\Delta _{2}(H)=1,d(v)=n-2}$ ${\displaystyle v\in V(H)}$ ${\displaystyle H}$ ${\displaystyle c=1}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle n^{O(n^{3/2})}}$ ${\displaystyle E(K_{n})}$ ${\displaystyle n}$

• Todo grafo libre de triángulo es un subgrafo de algún , ${\displaystyle C\in {\mathcal {C}}}$
• Cada uno tiene como máximo bordes. ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle (1-\delta ){n \choose 2}}$

Esto no es tan fuerte como el resultado que queremos mostrar, por lo que aplicaremos iterativamente el lema del contenedor. Supongamos que tenemos un contenedor con al menos triángulos. Podemos aplicar el lema del contenedor al subhipergrafo inducido . El grado promedio de es al menos , ya que cada triángulo en es una arista en , y este subgrafo inducido tiene como máximo vértices. Por lo tanto, podemos aplicar el lema con el parámetro , eliminar de nuestro conjunto de contenedores, reemplazándolo por este conjunto de contenedores, los contenedores que cubren . ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle \epsilon n^{3}}$ ${\displaystyle H[C]}$ ${\displaystyle H[C]}$ ${\displaystyle 6\epsilon n}$ ${\displaystyle C}$ ${\displaystyle H[C]}$ ${\displaystyle {n \choose 2}}$ ${\displaystyle c=1/\epsilon }$ ${\displaystyle C}$ ${\displaystyle {\mathcal {I}}(H[C])}$

Podemos seguir iterando hasta que tengamos una colección final de contenedores que contengan cada uno menos de triángulos. Observamos que esta colección no puede ser demasiado grande; todos nuestros subgrafos inducidos tienen como máximo vértices y un grado promedio de al menos , lo que significa que cada iteración da como máximo nuevos contenedores. Además, el tamaño del contenedor se reduce por un factor de cada vez, por lo que después de un número limitado (dependiendo de ) de iteraciones, el proceso iterativo terminará. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \epsilon n^{3}}$ ${\displaystyle {n \choose 2}}$ ${\displaystyle 6\epsilon n}$ ${\displaystyle n^{O(n^{3/2})}}$ ${\displaystyle 1-\delta }$ ${\displaystyle \epsilon }$

Véase también

Conjunto independiente (teoría de grafos)
Teorema de Szemerédi
Lema de regularidad de Szemerédi

Referencias

1. Kleitman, Daniel; Winston, Kenneth (1980). "El número asintótico de redes". Anales de Matemáticas Discretas . 6 : 243–249. doi :10.1016/S0167-5060(08)70708-8. ISBN 9780444860484.
2. Kleitman, Daniel; Winston, Kenneth (1982). "Sobre el número de grafos sin 4-ciclos". Matemáticas discretas . 31 (2): 167–172. doi : 10.1016/0012-365X(82)90204-7 .
3. Sapozhenko, Alejandro (2003). "La conjetura de Cameron-Erdos". Doklady Akademii Nauk . 393 : 749–752.
4. Sapozhenko, Alexander (2002). "Asintótica para el número de conjuntos sin suma en grupos abelianos". Doklady Akademii Nauk . 383 : 454–458.
5. Sapozhenko, Alexander (2005), "Sistemas de contenedores y problemas de enumeración", Algoritmos estocásticos: fundamentos y aplicaciones , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 1–13, ISBN 978-3-540-29498-6, consultado el 13 de febrero de 2022
6. Saxton, David; Thomason, Andrew (2015). "Contenedores hipergráficos". Inventiones Mathematicae . 201 (3): 925–992. arXiv : 1204.6595 . Código Bibliográfico :2015InMat.201..925S. doi :10.1007/s00222-014-0562-8. S2CID  119253715.
7. Balogh, József; Morris, Robert; Samotij, Wojciech (2015). "Conjuntos independientes en hipergrafos". Revista de la Sociedad Americana de Matemáticas . 28 (3): 669–709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID  15244650.
8. Samotij, Wojciech (2015). "Contar conjuntos independientes en gráficos". Revista europea de combinatoria . 48 : 5–18. arXiv : 1412.0940 . doi :10.1016/j.ejc.2015.02.005. S2CID  15850625.
9. Balogh, József; Morris, Robert; Samotij, Wojciech (2015). "Conjuntos independientes en hipergrafos". Revista de la Sociedad Americana de Matemáticas . 28 (3): 669–709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID  15244650.
10. Balogh, József; Morris, Robert; Samotij, Wojciech (2018). "El método de los hipergrafos contenedores". Actas del Congreso Internacional de Matemáticos: Río de Janeiro . arXiv : 1801.04584 .