Método de contenedor

El método de contenedores (hipergrafos) 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 predefinido de restricciones locales. Estas preguntas surgen de forma natural en la teoría extremal de grafos , la combinatoria aditiva , la geometría discreta , la teoría de la codificación y la teoría de Ramsey ; e incluyen algunos de los problemas más clásicos en los campos relacionados.

Estos problemas pueden formularse como preguntas del siguiente tipo: 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 ciertas restricciones de tamaño), ¿qué podemos decir sobre los conjuntos independientes de $H$ (es decir, aquellos subconjuntos de $V$ que no contienen ningún elemento de $E$ )? El lema del contenedor de hipergrafos proporciona un método para abordar este tipo de preguntas.

Historia

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

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

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

Idea principal y declaración informal

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

En los casos anteriores (y en muchos otros), generalmente existen dos clases naturales de problemas planteados 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. $\alpha (H)$ Sea el tamaño del conjunto independiente más grande de $H$ y supongamos que $H$ tiene $i(H)$ conjuntos independientes. Entonces,

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 independiente máximo. Estos límites están relativamente alejados entre sí a menos que $\alpha (H)$ es muy grande, cercano al 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 real; por lo tanto, el objetivo principal es mejorar los límites superiores de $i(H)$ .

El lema del contenedor de hipergrafos 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 de hipergrafos 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 término «contenedor» alude a esta última condición. Dichos contenedores suelen proporcionar un método eficaz para caracterizar la familia de conjuntos independientes (subconjuntos de los contenedores) y para enumerar los conjuntos independientes de un hipergrafo (simplemente considerando todos los subconjuntos posibles de un contenedor).

El lema del contenedor de hipergrafos logra la descomposición de contenedores 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. $S\subset I$ , llamada huella dactilar, con la propiedad de que $S\subset I\subset S\cup f(S)$ Entonces, los contenedores son la colección de conjuntos. $S\cup f(S)$ que surgen en el proceso anterior, y el pequeño tamaño de las huellas dactilares proporciona un buen control sobre el número de dichos conjuntos de contenedores.

Algoritmo de contenedor de grafos

Primero describimos un método para mostrar límites superiores fuertes sobre el número de conjuntos independientes en un grafo; esta exposición está adaptada de un estudio de Samotij ^{[ 8 ]} sobre el método del contenedor de grafos, empleado originalmente por Kleitman-Winston y Sapozhenko.

Notación

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

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

Algoritmo de Kleitman-Winston

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

Fijar el grafo $G$ , conjunto independiente $I\in \ell (G)$ y entero positivo $q\leq |I|$ .

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

Análisis

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

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

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 $r$ para obtener una cota sobre el número total de conjuntos independientes del grafo:

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 tratar de minimizar este límite superior, queremos elegir $q$ que equilibra/minimiza estos dos términos. Este resultado ilustra el valor de ordenar los vértices por grado máximo (para minimizar $|A(j_{1},\ldots j_{q})|$ ).

Lemas

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

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

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

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

lema del contenedor de hipergrafos

De manera informal, el lema del contenedor de hipergrafos nos dice que podemos asignar una huella digital pequeña. $S\subset I$ a cada conjunto independiente, de modo que todos los conjuntos independientes con la misma huella digital pertenezcan al mismo conjunto más grande, $C=f(S)$ , el contenedor asociado , cuyo tamaño está acotado lejos 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 superiormente su tamaño de una manera esencialmente óptima utilizando algunas propiedades simples del hipergrafo.

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

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

Declaración

Presentamos la versión de este lema que se encuentra en una obra de Balogh, Morris, Samotij y Saxton. ^{[ 9 ]}

Dejar ${\mathcal {H}}$ ser un $k$ Hipergrafo uniforme y supongamos que para cada $l\in \{1,2,\ldots ,k\}$ y algunos $b,r\in \mathbb {N}$ , tenemos eso $\Delta _{l}(H)\leq \left({\frac {b}{|V(H)|}}\right)^{l-1}{\frac {|E(H)|}{r}}$ Luego, hay una colección ${\mathcal {C}}\subset {\mathcal {P}}(V(H))$ y una función $f\colon {\mathcal {P}}(V(H))\rightarrow {\mathcal {C}}$ de tal manera que

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

Ejemplos de aplicaciones

Gráficos regulares

Límite superior del número de conjuntos independientes

Demostraremos que existe una constante absoluta $C$ tal que cada $n$ -vértice $d$ -gráfico regular $G$ Satisface $i(G)\leq 2^{\left(1+C{\sqrt {\frac {\log d}{d}}}\right){\frac {n}{2}}}$ .

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

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 $0\leq r\leq n$ da

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

,

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

Conjuntos libres de suma

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

Esto se deduce de nuestros límites anteriores sobre el número de conjuntos independientes en un grafo regular. Para ver esto, necesitaremos construir un grafo auxiliar. Primero observamos que, salvo términos de orden inferior, podemos restringir nuestro enfoque a conjuntos libres de suma con al menos $n^{2/3}$ elementos más pequeños que $n/2$ (ya que el número de subconjuntos en el complemento de este es como máximo $(n/2)^{n^{2/3}}2^{n/2+1}$ ).

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

(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 un ejemplo del uso del lema del contenedor de hipergrafos para responder a una pregunta enumerativa dando una cota superior asintóticamente ajustada sobre el número de grafos libres de triángulos con $n$ vértices. ^{[ 10 ]}

Declaración informal

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

Podemos construir un hipergrafo auxiliar $3 -uniforme$ $H$ con conjunto de vértices $V(H)=E(K_{n})$ y conjunto de bordes $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}}\}$ . Este hipergrafo "codifica" triángulos en el sentido de que la familia de grafos libres de triángulos en $n$ vértices es precisamente la colección de conjuntos independientes de este hipergrafo, ${\mathcal {I}}(H)$ .

El hipergrafo anterior tiene una buena distribución de grados : cada arista de $K_{n}$ y por lo tanto vértice en $V(H)$ está contenido exactamente $n-2$ triángulos y cada par de elementos en $V(H)$ está contenido en como máximo 1 triángulo. Por lo tanto, aplicando el lema del contenedor de hipergrafos (iterativamente), podemos demostrar que existe una familia de $n^{O(n^{3/2})}$ contenedores que contienen cada uno unos pocos triángulos que contienen cada grafo libre de triángulos/conjunto independiente del hipergrafo.

Límite superior para el número de grafos libres de triángulos

En primer lugar, especializamos el lema genérico de contenedor de hipergrafos a hipergrafos 3-uniformes de la siguiente manera:

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

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

Aplicando este lema de forma iterativa se obtiene el siguiente teorema (como se demuestra a continuación):

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

cada $G\in {\mathcal {G}}$ tiene menos que $\epsilon n^{3}$ triángulos,
cada gráfico sin triángulos en $n$ Los vértices están contenidos en algunos $G\in {\mathcal {G}}$ .

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

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

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

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

Véase también

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

Referencias

↑ Kleitman, Daniel; Winston, Kenneth (1980). «El número asintótico de retículos». Annals of Discrete Mathematics . 6 : 243–249 . doi : 10.1016/S0167-5060(08)70708-8 . ISBN 9780444860484.
↑ 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 .
^ Sapozhenko, Alejandro (2003). "La conjetura de Cameron-Erdos". Doklady Akademii Nauk . 393 : 749-752 .
↑ Sapozhenko, Alexander (2002). "Asintótica para el número de conjuntos libres de suma en grupos abelianos". Doklady Akademii Nauk . 383 : 454–458 .
↑ Sapozhenko, Alexander (2005), "Sistemas de contenedores y problemas de enumeración" , Algoritmos estocásticos: fundamentos y aplicaciones , Lecture Notes in Computer Science, vol. 3777, Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 1–13 , doi : 10.1007/11571155_1 , ISBN 978-3-540-29498-6, consultado el 13 de febrero de 2022
↑ Saxton, David; Thomason, Andrew (2015). "Contenedores de hipergrafos". Inventiones Mathematicae . 201 (3): 925– 992. arXiv : 1204.6595 . Bibcode : 2015InMat.201..925S . doi : 10.1007/s00222-014-0562-8 . S2CID 119253715 .
↑ Balogh, József; Morris, Robert; Samotij, Wojciech (2015). "Conjuntos independientes en hipergrafos" . Journal of the American Mathematical Society . 28 (3): 669– 709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650 .
↑ 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 .
↑ Balogh, József; Morris, Robert; Samotij, Wojciech (2015). "Conjuntos independientes en hipergrafos" . Journal of the American Mathematical Society . 28 (3): 669– 709. arXiv : 1204.6530 . doi : 10.1090/S0894-0347-2014-00816-X . S2CID 15244650 .
↑ Balogh, József; Morris, Robert; Samotij, Wojciech (2018). "El método de los contenedores de hipergrafos". Actas del Congreso Internacional de Matemáticos: Río de Janeiro . arXiv : 1801.04584 .

[1] Kleitman, Daniel; Winston, Kenneth (1980). «El número asintótico de retículos». Annals of Discrete Mathematics . 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 libres de 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 , Lecture Notes in Computer Science, vol. 3777, Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 1–13 , doi : 10.1007/11571155_1 , ISBN 978-3-540-29498-6, consultado el 13 de febrero de 2022

[6] Saxton, David; Thomason, Andrew (2015). "Contenedores de hipergrafos". Inventiones Mathematicae . 201 (3): 925– 992. arXiv : 1204.6595 . Bibcode : 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" . Journal of the American Mathematical Society . 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" . Journal of the American Mathematical Society . 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 contenedores de hipergrafos". Actas del Congreso Internacional de Matemáticos: Río de Janeiro . arXiv : 1801.04584 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]