lema de eliminación de hipergrafos

En teoría de grafos , el lema de eliminación de hipergrafos establece que cuando un hipergrafo contiene pocas copias de un subhipergrafo dado, todas las copias pueden eliminarse eliminando un pequeño número de hiperaristas. Es una generalización del lema de eliminación de grafos . El caso especial en el que el grafo es un tetraedro se conoce como el lema de eliminación de tetraedros. Fue demostrado por primera vez por Nagle, Rödl, Schacht y Skokan ^{[ 1 ]} e, independientemente, por Gowers ^{[ 2 ] .}

El lema de eliminación de hipergrafos se puede utilizar para demostrar resultados como el teorema de Szemerédi ^{[ 1 ]} y el teorema de Szemerédi multidimensional. ^{[ 1 ]}

Dejar${\displaystyle H}$ser un${\displaystyle r}$Hipergrafo uniforme (cada arista conecta exactamente r vértices) con${\displaystyle h}$vértices. El lema de eliminación de hipergrafos establece que para cualquier${\displaystyle \varepsilon >0}$existe${\displaystyle \delta =\delta (r,m,\varepsilon)>0}$de tal manera que para cualquier ${\displaystyle r}$-uniforme,${\displaystyle n}$Hipergrafo de vértices${\displaystyle G}$con menos de${\displaystyle \delta n^{h}}$subhipergrafos isomorfos a${\displaystyle H}$es posible eliminar todas las copias de${\displaystyle H}$eliminando como máximo${\displaystyle \varepsilon n^{r}}$bordes.

Una formulación equivalente es que, para cualquier hipergrafo${\displaystyle G}$con${\displaystyle o(n^{h})}$copias de${\displaystyle H}$, podemos eliminar todas las copias de${\displaystyle H}$de${\displaystyle G}$eliminando${\displaystyle o(n^{r})}$hiperbordes.

El lema de eliminación de grafos es un caso especial con${\displaystyle r=2}$.

La idea general de la demostración es similar a la del lema de eliminación de grafos . Demostramos una versión hipergráfica del lema de regularidad de Szemerédi (particionar hipergrafos en bloques pseudoaleatorios) y un lema de conteo (estimar el número de hipergrafos en un bloque pseudoaleatorio apropiado). La dificultad clave en la demostración es definir la noción correcta de regularidad de hipergrafos. Hubo múltiples intentos ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ]} para definir "partición" y "bloques pseudoaleatorios (regulares)" en un hipergrafo, pero ninguno de ellos es capaz de dar un lema de conteo fuerte. La primera definición correcta del lema de regularidad de Szemerédi para hipergrafos generales es dada por Rödl et al. ^{[ 1 ].}

En el lema de regularidad de Szemerédi , las particiones se realizan en vértices (1-hiperarista) para regular las aristas (2-hiperaristas). Sin embargo, para${\displaystyle k>2}$si simplemente regulamos${\displaystyle k}$-hiperaristas usando solo 1 hiperarista, perderemos información de todas${\displaystyle j}$-hiperbordes en el medio donde${\displaystyle 1<j<k}$y no logran encontrar un lema de conteo. ^{[ 13 ]} La versión correcta tiene que particionar${\displaystyle (k-1)}$-hiperbordes para regular${\displaystyle k}$-hiperbordes. Para obtener más control de los${\displaystyle (k-1)}$-hiperbordes, podemos ir un nivel más profundo y particionar en${\displaystyle (k-2)}$-hiperaristas para regularlas, etc. Al final, llegaremos a una estructura compleja de regulación de hiperaristas.

Por ejemplo, demostramos una versión informal de 3-hipergrafos del lema de regularidad de Szemerédi, presentado por primera vez por Frankl y Rödl. ^{[ 14 ]} Consideremos una partición de aristas${\displaystyle E(K_{n})=G_{1}^{(2)}\cup \dots \cup G_{l}^{(2)}}$de tal manera que para la mayoría de los tríos${\displaystyle (i,j,k),}$hay muchos triángulos encima de${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right).}$Decimos que${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)}$es "pseudoaleatorio" en el sentido de que para todos los subgrafos${\displaystyle A_{i}^{(2)}\subset G_{i}^{(2)}}$con no muy pocos triángulos encima de${\displaystyle \left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right),}$tenemos

${\displaystyle \left|d\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)-d\left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right)\right|\leq \varepsilon ,}$

dónde${\displaystyle d(X,Y,Z)}$denota la proporción de${\displaystyle 3}$-hiperborde uniforme en${\displaystyle G^{(3)}}$entre todos los triángulos encima de${\displaystyle (X,Y,Z)}$.

Luego definimos una partición regular como una partición en la que las ternas de partes que no son regulares constituyen como máximo una${\displaystyle \varepsilon }$fracción de todas las ternas de partes en la partición.

Además de esto, necesitamos regularizar aún más${\displaystyle G_{1}^{(2)},\dots ,G_{l}^{(2)}}$mediante una partición del conjunto de vértices. Como resultado, tenemos los datos totales de regularidad del hipergrafo de la siguiente manera:

1. una partición de${\displaystyle E(K_{n})}$en gráficos de tal manera que${\displaystyle G^{(3)}}$se sitúa pseudoaleatoriamente en la parte superior;
2. una partición de${\displaystyle V(G)}$de tal manera que los gráficos en (1) son extremadamente pseudoaleatorios (de una forma que se asemeja al lema de regularidad de Szemerédi ).

Tras demostrar el lema de regularidad de hipergrafos, podemos demostrar un lema de conteo de hipergrafos. El resto de la demostración procede de forma similar a la del lema de eliminación de grafos .

Dejar${\displaystyle r_{k}(N)}$sea ​​el tamaño del subconjunto más grande de${\displaystyle \{1,\ldots ,N\}}$que no contiene una longitud${\displaystyle k}$progresión aritmética. El teorema de Szemerédi establece que,${\displaystyle r_{k}(N)=o(N)}$para cualquier constante${\displaystyle k}$La idea principal de la demostración es que construimos un hipergrafo a partir de un subconjunto sin ninguna longitud.${\displaystyle k}$progresión aritmética, luego use el lema de eliminación de grafos para mostrar que este grafo no puede tener demasiadas hiperaristas, lo que a su vez muestra que el subconjunto original no puede ser demasiado grande.

Dejar${\displaystyle A\subset \{1,\ldots ,N\}}$ser un subconjunto que no contiene ninguna longitud${\displaystyle k}$progresión aritmética. Dejemos${\displaystyle M=k^{2}N+1}$ser un número entero suficientemente grande . Podemos pensar en${\displaystyle A}$como un subconjunto de${\displaystyle \mathbb {Z} /M\mathbb {Z} }$. Claramente, si${\displaystyle A}$no tiene longitud${\displaystyle k}$progresión aritmética en${\displaystyle \mathbb {Z} }$, tampoco tiene longitud${\displaystyle k}$progresión aritmética en${\displaystyle \mathbb {Z} /M\mathbb {Z} }$.

Construiremos un${\displaystyle k}$-partito${\displaystyle (k-1)}$Hipergrafo uniforme${\displaystyle G}$de${\displaystyle A}$con piezas${\displaystyle V_{1},V_{2},\ldots ,V_{k}}$, todos los cuales son${\displaystyle M}$conjuntos de vértices de elementos indexados por${\displaystyle \mathbb {Z} /M\mathbb {Z} }$. Para cada${\displaystyle 1\leq i\leq k}$, añadimos una hiperarista entre vértices${\displaystyle (v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}}$si y solo si${\displaystyle \sum _{j\neq i}(j-i)v_{j}\in A.}$Dejar${\displaystyle H}$ser el completo${\displaystyle k}$-partito${\displaystyle (k-1)}$Hipergrafo uniforme. Si${\displaystyle G}$contiene una copia isomorfa de${\displaystyle H}$con vértices${\displaystyle v_{1},\ldots ,v_{k}}$, entonces${\displaystyle \alpha _{i}=\sum _{j\neq i}(j-i)v_{j}\in A}$para cualquier${\displaystyle 1\leq i\leq j}$Sin embargo, tenga en cuenta que${\displaystyle \alpha _{i}}$es una longitud${\displaystyle k}$progresión aritmética con diferencia común${\displaystyle \alpha _{i+1}-\alpha _{i}=-\sum _{j}v_{j}}$. Desde${\displaystyle A}$no tiene longitud${\displaystyle k}$progresión aritmética, debe ser el caso que${\displaystyle \alpha _{1}=\cdots =\alpha _{k}}$, entonces${\displaystyle \sum _{j}v_{j}=0}$.

Por lo tanto, para cada hiperarista${\displaystyle (v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}}$, podemos encontrar una copia única de${\displaystyle H}$que esta ventaja radica en encontrar${\displaystyle v_{i}=-\sum _{j\neq i}v_{j}}$. El número de copias de${\displaystyle H}$en${\displaystyle G}$igual${\displaystyle {\frac {1}{k}}e(G)=O(N^{k-1})=o(N^{k})}$Por lo tanto, mediante el lema de eliminación de hipergrafos, podemos eliminar${\displaystyle o(N^{k-1})}$bordes para eliminar todas las copias de${\displaystyle H}$en${\displaystyle G}$. Dado que cada hiperarista de${\displaystyle G}$está en una copia única de${\displaystyle H}$, para eliminar todas las copias de${\displaystyle H}$en${\displaystyle G}$, necesitamos eliminar al menos${\displaystyle e(G)/k}$bordes. Por lo tanto,${\displaystyle e(G)=o(N^{k-1})}$.

El número de hiperaristas en${\displaystyle G}$es${\displaystyle kM^{k-2}|A|=o(N^{k-1})}$, lo que concluye que${\displaystyle |A|=o(N)}$.

Este método generalmente no proporciona una buena cota cuantitativa, ya que las constantes ocultas en el lema de eliminación de hipergrafos involucran la función de Ackermann inversa . Para una mejor cota cuantitativa, Leng, Sah y Sawhney demostraron que${\displaystyle |A|\leq {\frac {N}{\exp(-(\log \log N)^{c_{k}})}}}$por alguna constante${\displaystyle c_{k}}$Dependiendo de${\displaystyle k}$. ^{[ 15 ]} Es el mejor límite para${\displaystyle k\geq 5}$hasta ahora.

• El lema de eliminación de hipergrafos se utiliza para demostrar el teorema de Szemerédi multidimensional de J. Solymosi. ^{[ 16 ]} La afirmación es que cualquier para cualquier subconjunto finito${\displaystyle S}$de${\displaystyle \mathbb {Z} ^{r}}$, cualquier${\displaystyle \delta >0}$y cualquier${\displaystyle n}$lo suficientemente grande, cualquier subconjunto de${\displaystyle [n]^{r}}$de tamaño al menos${\displaystyle \delta n^{r}}$contiene un subconjunto de la forma${\displaystyle a\cdot S+d}$, es decir, una copia dilatada y traducida de${\displaystyle S}$El teorema de las esquinas es un caso especial cuando${\displaystyle S=\{(0,0),(0,1),(1,0)\}}$.
• También se utiliza para demostrar el teorema de Szemerédi del polinomio, el teorema de Szemerédi del campo finito y el teorema de Szemerédi del grupo abeliano finito . ^{[ 17 ] [ 18 ]}

• lema de eliminación de grafos
• Teorema de Szemerédi
• Problemas que implican progresiones aritméticas