Método de regularidad de hipergrafos

En matemáticas, el método de regularidad de hipergrafos es una herramienta poderosa en la teoría extremal de grafos que se refiere a la aplicación combinada del lema de regularidad de hipergrafos y el lema de conteo asociado. Es una generalización del método de regularidad de grafos, que se refiere al uso de los lemas de regularidad y conteo de Szemerédi .

De manera muy informal, el lema de regularidad de hipergrafos descompone cualquier dado $k$ - hipergrafo uniforme en un objeto de tipo aleatorio con partes acotadas (con nociones apropiadas de acotación y aleatoriedad) que suele ser más fácil de manejar. Por otro lado, el lema de conteo de hipergrafos estima el número de hipergrafos de una clase de isomorfismo dada en algunas colecciones de las partes de tipo aleatorio. Esta es una extensión del lema de regularidad de Szemerédi que particiona cualquier grafo dado en un número acotado de partes, de modo que las aristas entre las partes se comportan casi aleatoriamente. De manera similar, el lema de conteo de hipergrafos es una generalización del lema de conteo de grafos que estima el número de copias de un grafo fijo como subgrafo de un grafo mayor.

Existen varias formulaciones distintas del método, todas las cuales implican el lema de eliminación de hipergrafos y otros resultados importantes, como el teorema de Szemerédi , así como algunas de sus extensiones multidimensionales. Las siguientes formulaciones se deben a V. Rödl , B. Nagle, J. Skokan, M. Schacht y Y. Kohayakawa , ^{[ 1 ]} para versiones alternativas véase Tao (2006), ^{[ 2 ]} y Gowers (2007). ^{[ 3 ]}

Definiciones

Para enunciar formalmente la regularidad del hipergrafo y los lemas de conteo, necesitamos definir varios términos bastante técnicos para formalizar las nociones apropiadas de pseudoaleatoriedad (similitud aleatoria) y acotación, así como para describir los bloques y particiones de tipo aleatorio.

Notación

$K_{j}^{(k)}$ denota un $k$ -camarilla uniforme en $j$ vértices.
${\mathcal {G}}^{(j)}$ es un $l$ -partito $j$ -grafo en partición de vértices ${\mathcal {G}}^{(1)}=V_{1}\sqcup \ldots \sqcup V_{l}$ .
${\mathcal {K}}_{j}({\mathcal {G}}^{(i)})$ es la familia de todos $j$ conjuntos de vértices de -elementos que abarcan la clique $K_{j}^{(i)}$ en ${\mathcal {G}}^{(i)}$ . En particular, ${\mathcal {K}}_{j}({\mathcal {G}}^{(1)})=K_{l}^{(j)}(V_{1},\ldots ,V_{l})$ es un completo $l$ -partito $j$ -gráfico.

A continuación se define una noción importante de densidad relativa, que describe aproximadamente la fracción de $j$ -bordes abarcados por $(j-1)$ -aristas que están en el hipergrafo. Por ejemplo, cuando $j=3$ la cantidad $d({\mathcal {G}}^{(3)}\vert \mathbf {Q} ^{(2)})$ es igual a la fracción de triángulos formados por 2 aristas en el subhipergrafo que son 3 aristas.

Definición [Densidad relativa]. Para $j\geq 3$ , corregir algunas clases $V_{i_{1}},\ldots ,V_{i_{j}}$ de ${\mathcal {G}}^{(1)}$ con $1\leq i_{1}<\ldots <i_{j}\leq l$ . Suponer $r\geq 1$ es un número entero. Sea $\mathbf {Q} ^{(j-1)}=\{Q_{1}^{(j-1)},\ldots ,Q_{r}^{(j-1)}\}$ ser un subhipergrafo del inducido $j$ grafo -partito ${\mathcal {G}}^{(j-1)}[V_{i_{1}},\ldots ,V_{i_{j}}]$ Definir la densidad relativa $d\left({\mathcal {G}}^{(j)}\vert \mathbf {Q} ^{(j-1)}\right)={\frac {\left|{\mathcal {G}}^{(j)}\cap \cup _{s\in [r]}{\mathcal {K}}_{j}(Q_{s}^{j-1})\right|}{\left|\cup _{s\in [r]}{\mathcal {K}}_{j}(Q_{s}^{j-1})\right|}}$ .

Lo que sigue es la noción apropiada de pseudoaleatoriedad que utilizará el método de regularidad. De manera informal, por este concepto de regularidad, $(j-1)$ -bordes ( ${\mathcal {G}}^{(j-1)}$ ) tener cierto control sobre $j$ -bordes ( ${\mathcal {G}}^{(j)}$ ). Más precisamente, esto define un entorno donde la densidad de $j$ Las aristas en los subhipergrafos grandes son aproximadamente las mismas que cabría esperar basándose únicamente en la densidad relativa. Formalmente,

Definición [( $\delta _{j},d_{j},r$ )-regularidad]. Supongamos que $\delta _{j},d_{j}$ son números reales positivos y $r\geq 1$ es un número entero. ${\mathcal {G}}^{(j)}$ es ( $\delta _{j},d_{j},r$ )-regular con respecto a ${\mathcal {G}}^{(j-1)}$ si para cualquier elección de clases $V_{i_{1}},\ldots ,V_{i_{j}}$ y cualquier colección de subhipergrafos $\mathbf {Q} ^{(j-1)}=\{Q_{1}^{(j-1)},\ldots ,Q_{r}^{(j-1)}\}$ de ${\mathcal {G}}^{(j-1)}[V_{i_{1}},\ldots ,V_{i_{j}}]$ satisfactorio $\left|\cup _{s\in [r]}{\mathcal {K}}_{j}(Q_{s})^{(j-1)}\right|\geq \delta _{j}\left|{\mathcal {K}}_{j}({\mathcal {G}}^{(j-1)}[V_{i_{1}},\ldots ,V_{i_{j}}])\right|$ tenemos $d({\mathcal {G}}^{(j)}\vert \mathbf {Q} ^{(j-1)})=d_{j}\pm \delta _{j}$ .

En términos generales, lo siguiente describe los bloques pseudoaleatorios en los que el lema de regularidad de hipergrafos descompone cualquier hipergrafo suficientemente grande. En la regularidad de Szemerédi, las aristas de orden 2 se regularizan frente a las aristas de orden 1 (vértices). En esta noción generalizada, $j$ -los bordes se regularizan frente a $(j-1)$ -bordes para todos $2\leq j\leq h$ . Más precisamente, esto define una noción de hipergrafo regular llamado $(l,h)$ -complejo, en el que existe de $j$ -edge implica la existencia de todos los subyacentes $(j-1)$ -aristas, así como su regularidad relativa. Por ejemplo, si $\{x,y,z\}$ es un 3-arista entonces $\{x,y\}$ , $\{x,z\}$ , y $\{y,z\}$ son 2-aristas en el complejo. Además, la densidad de 3-aristas sobre todos los triángulos posibles formados por 2-aristas es aproximadamente la misma en cada colección de subhipergrafos.

Definición [ $(\delta ,\mathbf {d} ,r)$ -regular $(l,h)$ -complejo]. Un $(l,h)$ -complejo $\mathbf {G}$ es un sistema $\{{\mathcal {G}}^{(j)}\}_{j=1}^{h}$ de $l$ -partito $j$ gráficos ${\mathcal {G}}^{(j)}$ satisfactorio ${\mathcal {G}}^{(j)}\subset {\mathcal {K}}_{j}({\mathcal {G}}^{(j-1)})$ . Dados vectores de números reales positivos $\delta =(\delta _{2},\ldots ,\delta _{h})$ , $\mathbf {d} =(d_{2},\ldots ,d_{h})$ y un número entero $r\geq 1$ , decimos $(l,h)$ -complejo es $(\delta ,\mathbf {d} ,r)$ -regular si
Para cada $1\leq i_{1}<i_{2}\leq l$ , ${\mathcal {G}}^{(2)}[V_{i_{1}},V_{i_{2}}]$ es $\delta _{2}$ -regular con densidad $d_{2}\pm \delta _{2}$ .
Para cada $3\leq j\leq h$ , ${\mathcal {G}}^{(j)}$ es ( $\delta _{j},d_{j},r$ )-regular con respecto a ${\mathcal {G}}^{(j-1)}$ .

A continuación se describe la partición equitativa que inducirá el lema de regularidad del hipergrafo. $(\mu ,\delta ,\mathbf {d} ,r)$ La familia equitativa de particiones es una secuencia de particiones de 1-aristas (vértices), 2-aristas (pares), 3-aristas (triples), etc. Esta es una distinción importante con respecto a la partición obtenida mediante el lema de regularidad de Szemerédi, donde solo se particionan los vértices. De hecho, Gowers ^{[ 3 ]} demostró que la partición de vértices por sí sola no proporciona una noción de regularidad suficientemente fuerte como para implicar el lema de conteo de hipergrafos.

Definición [ $(\mu ,\delta ,\mathbf {d} ,r)$ -partición equitativa]. $\mu >0$ ser un número real, $r\geq 1$ sea un número entero, y $\delta =(\delta _{2},\ldots ,\delta _{k-1})$ , $\mathbf {d} =(d_{2},\ldots ,d_{k-1})$ sean vectores de números reales positivos. $\mathbf {a} =(a_{1},\ldots ,a_{k-1})$ sea un vector de enteros positivos y $V$ frijol $n$ Conjunto de vértices de -elementos. Decimos que una familia de particiones ${\mathcal {P}}={\mathcal {P}}(k-1,\mathbf {a} )=\{{\mathcal {P}}^{(1)}\,\ldots ,{\mathcal {P}}^{(k-1)}\}$ en $V$ es $(\mu ,\delta ,\mathbf {d} ,r)$ -equitativo si cumple con lo siguiente:
${\mathcal {P}}^{(1)}=\{V_{i}\colon i\in [a_{1}]\}$ es partición equitativa de vértices de $V$ . Eso es $|V_{1}|\leq \ldots \leq |V_{a_{1}}|\leq |V_{1}|+1$ .
${\mathcal {P}}^{(j)}$ particiones ${\mathcal {K}}_{j}({\mathcal {G}}^{(1)})=K_{a_{1}}^{(j)}(V_{1},\ldots ,V_{a_{1}})$ para que si $P_{1}^{(j-1)},\ldots ,P_{j}^{(j-1)}\in {\mathcal {P}}^{(j-1)}$ y ${\mathcal {K}}_{j}(\cup _{i=1}^{j}P_{i}^{(j-1)})\neq \emptyset$ entonces ${\mathcal {K}}_{j}(\cup _{i=1}^{j}P_{i}^{(j-1)})$ se divide en como máximo $a_{j}$ partes, todas las cuales son miembros ${\mathcal {P}}^{(j)}$ .
Para todos excepto como máximo $\mu n^{k}$ $k$ -tuplas $K\in {\binom {V}{k}}$ hay algo único $(\delta ,\mathbf {d} ,r)$ -regular $(k,k-1)$ -complejo $\mathbf {P} =\{P^{(j)}\}_{j=1}^{k-1}$ de tal manera que $P^{(j)}$ tiene como miembros ${\binom {k}{j}}$ diferentes clases de partición de ${\mathcal {P}}^{(j)}$ y $K\in {\mathcal {K}}_{k}(P^{(k-1)})\subset \ldots \subset {\mathcal {K}}_{k}(P^{(1)})$ .

Finalmente, lo siguiente define lo que significa para un $k$ Un hipergrafo uniforme debe ser regular con respecto a una partición. En particular, esta es la definición principal que describe el resultado del lema de regularidad de hipergrafos que se presenta a continuación.

Definición [Regularidad con respecto a una partición]. Decimos que una $k$ -gráfico ${\mathcal {H}}^{(k)}$ es $(\delta _{k},r)$ -regular con respecto a una familia de particiones ${\mathcal {P}}$ si todos excepto como máximo $\delta _{k}n^{k}$ $k-$ bordes $K$ de ${\mathcal {H}}^{(k)}$ tener la propiedad que $K\in {\mathcal {K}}_{k}({\mathcal {G}}^{(1)})$ y si $\mathbf {P} =\{P^{(j)}\}_{j=1}^{k-1}$ es único $(k,k-1)$ -complejo para el cual $K\in {\mathcal {K}}_{k}(P^{(k-1)})$ , entonces ${\mathcal {H}}^{(k)}$ es $(\delta _{k},d({\mathcal {H}}^{(k)}\vert P^{(k-1)}),r)$ regular con respecto a ${\mathcal {P}}$ .

Declaraciones

Lema de regularidad de hipergrafos

Para todos los reales positivos $\mu$ , $\delta _{k}$ y funciones $r\,\colon \mathbb {N} \times (0,1]^{k-2}\to \mathbb {N}$ , $\delta _{j}\,\colon (0,1]^{k-j}\to (0,1]$ para $j=2,\ldots ,k-1$ existe $T_{0}$ y $n_{0}$ de modo que se cumple lo siguiente. Para cualquier $k$ Hipergrafo uniforme ${\mathcal {H}}^{(k)}$ en $n\geq n_{0}$ vértices, existe una familia de particiones ${\mathcal {P}}={\mathcal {P}}(k-1,\mathbf {a} )$ y un vector $\mathbf {d} =(d_{2},\ldots ,d_{k-1})$ para que, por $r=r(a_{1},\mathbf {d} )$ y $\mathbf {\delta } =(\delta _{2},\ldots ,\delta _{k-1})$ dónde $\delta _{j}=\delta _{j}(d_{j},\ldots ,d_{k-1})$ a pesar de $j$ , se cumple lo siguiente.

${\mathcal {P}}$ es un $(\mu ,\mathbf {\delta } ,\mathbf {d} ,r)$ -familia equitativa de particiones y $a_{i}\leq T_{0}$ por cada $i=1,\ldots ,k-1$ .
${\mathcal {H}}^{(k)}$ es $(\delta _{k},r)$ regular con respecto a ${\mathcal {P}}$ .

lema de conteo de hipergrafos

Para todos los números enteros $2\leq k\leq l$ Se cumple lo siguiente: $\forall \gamma >0\;\;\forall d_{k}>0\;\;\exists \delta _{k}>0\;\;\forall d_{k-1}>0\;\;\exists \delta _{k-1}>0\;\cdots \;\forall d_{2}>0\;\;\exists \delta _{2}>0$ y hay números enteros $r$ y $m_{0}$ para que, con $\mathbf {d} =(d_{2},\ldots ,d_{k})$ , $\delta =(\delta _{2},\ldots ,\delta _{k})$ , y $m\geq m_{0}$ ,

si $\mathbf {G} =\{{\mathcal {G}}^{(j)}\}_{j=1}^{k}$ es un $(\delta ,\mathbf {d} ,r)$ -regular $(l,k)$ complejo con partición de vértices ${\mathcal {G}}^{(1)}=V_{1}\cup \cdots \cup V_{l}$ y $|V_{i}|=m$ , entonces

$\left|{\mathcal {K}}_{l}({\mathcal {G}}^{(k)})\right|=(1\pm \gamma )\prod _{h=2}^{k}d_{h}^{\binom {l}{h}}\times m^{l}$ .

Aplicaciones

La principal aplicación a través de la cual se derivan la mayoría de las demás es el lema de eliminación de hipergrafos , que establece aproximadamente que dado fijo ${\mathcal {F}}^{(k)}$ y grande ${\mathcal {H}}^{(k)}$ $k$ -hipergrafos uniformes, si ${\mathcal {H}}^{(k)}$ contiene pocas copias de ${\mathcal {F}}^{(k)}$ , entonces se pueden eliminar algunos hiperbordes en ${\mathcal {H}}^{(k)}$ eliminar todas las copias de ${\mathcal {F}}^{(k)}$ Para decirlo de manera más formal,

lema de eliminación de hipergrafos

A pesar de $l\geq k\geq 2$ y cada $\mu >0$ , existe $\zeta >0$ y $n_{0}>0$ de modo que se cumple lo siguiente. Supongamos ${\mathcal {F}}^{(k)}$ es un $k$ -hipergrafo uniforme en $l$ vértices y ${\mathcal {H}}^{(k)}$ ¿Es eso? $n\geq n_{0}$ vértices. Si ${\mathcal {H}}^{(k)}$ contiene como máximo $\zeta n^{l}$ copias de ${\mathcal {F}}^{(k)}$ , entonces se puede eliminar $\mu n^{k}$ hiperbordes en ${\mathcal {H}}^{(k)}$ para hacerlo ${\mathcal {F}}^{(k)}$ -gratis.

Una de las motivaciones originales para el método de regularidad de grafos fue demostrar el teorema de Szemerédi , que establece que todo subconjunto denso de $\mathbb {Z}$ contiene una progresión aritmética de longitud arbitraria. De hecho, mediante una aplicación relativamente simple del lema de eliminación de triángulos , se puede demostrar que todo subconjunto denso de $\mathbb {Z}$ Contiene una progresión aritmética de longitud 3.

El método de regularidad de hipergrafos y el lema de eliminación de hipergrafos pueden demostrar análogos de alta dimensión y de anillos de la versión de densidad de los teoremas de Szemerédi, demostrados originalmente por Furstenberg y Katznelson. ^{[ 4 ]} De hecho, este enfoque proporciona las primeras cotas cuantitativas para los teoremas.

Este teorema implica aproximadamente que cualquier subconjunto denso de $\mathbb {Z} ^{d}$ contiene cualquier patrón finito de $\mathbb {Z} ^{d}$ . El caso cuando $d=1$ y el patrón es una progresión aritmética de longitud alguna longitud es equivalente al teorema de Szemerédi.

Teorema de Furstenberg y Katznelson
Fuente: ^{[ 4 ]}
Dejar $T$ ser un subconjunto finito de $\mathbb {R} ^{d}$ y dejar $\delta >0$ Se da un valor. Entonces existe un subconjunto finito. $C\subset \mathbb {R} ^{d}$ de tal manera que cada $Z\subset C$ con $|Z|>\delta |C|$ contiene una copia homotética de $T$ . (es decir, conjunto de formularios) $z+\lambda T$ , para algunos $z\in \mathbb {R} ^{d}$ y $t\in \mathbb {R}$ )
Además, si $T\subset [-t;t]^{d}$ para algunos $t\in \mathbb {N}$ , entonces existe $N_{0}\in \mathbb {N}$ de tal manera que $C=[-N,N]^{d}$ tiene esta propiedad para todos $N\geq N_{0}$ .

Otra posible generalización que puede demostrarse mediante el lema de eliminación es cuando se permite que la dimensión crezca.

Teorema de Tengan, Tokushige, Rödl y Schacht
Dejar $A$ sea un anillo finito. Para cada $\delta >0$ , existe $M_{0}$ de tal manera que, para $M\geq M_{0}$ cualquier subconjunto $Z\subset A^{M}$ con $|Z|>\delta |A^{M}|$ contiene una clase lateral de una copia isomorfa de $A$ (como una izquierda $A$ -módulo).
En otras palabras, hay algunos $\mathbf {r} ,\mathbf {u} \in A^{M}$ de tal manera que $r+\varphi (A)\subset Z$ , dónde $\varphi \colon A\to A^{M}$ , $\varphi (a)=a\mathbf {u}$ es una inyección.

Referencias

↑ Rödl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (2005-06-07). "El método de regularidad de hipergrafos y sus aplicaciones" . Actas de la Academia Nacional de Ciencias . 102 (23): 8109– 8113. doi : 10.1073/pnas.0502771102 . ISSN 0027-8424 . PMC 1149431. PMID 15919821 .
↑ Tao, Terence (1 de octubre de 2006). "Una variante del lema de eliminación de hipergrafos" . Journal of Combinatorial Theory . Serie A. 113 (7): 1257–1280 . arXiv : math/0503572 . doi : 10.1016/j.jcta.2005.11.006 . ISSN 0097-3165 .
1 2 Gowers, William (2007-11-01). "Regularidad de hipergrafos y el teorema de Szemerédi multidimensional" . Annals of Mathematics . 166 (3): 897– 946. arXiv : 0710.3032 . doi : 10.4007/annals.2007.166.897 . ISSN 0003-486X .
1 2 Fürstenberg, Hillel; Katznelson, Yitzhak (1978). "Un teorema ergódico de Szemeredi para transformaciones conmutadas". Revista de Análisis Matemático . 34 : 275– 291. doi : 10.1007/BF02790016 .

[1] Rödl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (2005-06-07). "El método de regularidad de hipergrafos y sus aplicaciones" . Actas de la Academia Nacional de Ciencias . 102 (23): 8109– 8113. doi : 10.1073/pnas.0502771102 . ISSN 0027-8424 . PMC 1149431. PMID 15919821 .

[2] Tao, Terence (1 de octubre de 2006). "Una variante del lema de eliminación de hipergrafos" . Journal of Combinatorial Theory . Serie A. 113 (7): 1257–1280 . arXiv : math/0503572 . doi : 10.1016/j.jcta.2005.11.006 . ISSN 0097-3165 .

[:1-3] 1 2 Gowers, William (2007-11-01). "Regularidad de hipergrafos y el teorema de Szemerédi multidimensional" . Annals of Mathematics . 166 (3): 897– 946. arXiv : 0710.3032 . doi : 10.4007/annals.2007.166.897 . ISSN 0003-486X .

[:0-4] 1 2 Fürstenberg, Hillel; Katznelson, Yitzhak (1978). "Un teorema ergódico de Szemeredi para transformaciones conmutadas". Revista de Análisis Matemático . 34 : 275– 291. doi : 10.1007/BF02790016 .

[ 1 ]

[ 2 ]