Discrepancia de hipergrafos

La discrepancia de hipergrafos es un área de la teoría de la discrepancia que estudia la discrepancia de sistemas de conjuntos generales.

En el contexto clásico, nuestro objetivo es particionar los vértices de un hipergrafo.${\displaystyle {\mathcal {H}}=(V,{\mathcal {E}})}$en dos clases de tal manera que idealmente cada hiperarista contenga el mismo número de vértices en ambas clases. Una partición en dos clases puede representarse mediante una coloración.${\displaystyle \chi \colon V\rightarrow \{-1,+1\}}$Llamamos colores −1 y +1 . Las clases de color${\displaystyle \chi ^{-1}(-1)}$y${\displaystyle \chi ^{-1}(+1)}$formen la partición correspondiente. Para una hiperarista${\displaystyle E\in {\mathcal {E}}}$, colocar

${\displaystyle \chi (E):=\sum _ {v\in E}\chi (v).}$

La discrepancia de${\displaystyle {\mathcal {H}}}$con respecto a${\displaystyle \chi }$y la discrepancia de${\displaystyle {\mathcal {H}}}$se definen por

${\displaystyle \operatorname {disco} ({\mathcal {H}},\chi ):=\;\max _{E\in {\mathcal {E}}}|\chi (E)|,}$

${\displaystyle \operatorname {disc} ({\mathcal {H}}):=\min _{\chi :V\rightarrow \{-1,+1\}}\operatorname {disc} ({\mathcal {H}},\chi ).}$

Estas nociones, así como el término «discrepancia», parecen haber aparecido por primera vez en un artículo de Beck . ^{[ 1 ]} Resultados anteriores sobre este problema incluyen la famosa cota inferior de la discrepancia de progresiones aritméticas de Roth ^{[ 2 ]} y cotas superiores para este problema y otros resultados de Erdős y Spencer ^{[ 3 ] [ 4 ]} y Sárközi. ^{[ 5 ] : 39} En ese momento, los problemas de discrepancia se denominaban problemas cuasi- Ramsey .

Para comprender mejor este concepto, veamos algunos ejemplos.

• Si todos los bordes de${\displaystyle {\mathcal {H}}}$intersecan trivialmente, es decir${\displaystyle E_{1}\cap E_{2}=\varnothing }$para cualesquiera dos bordes distintos${\displaystyle E_{1},E_{2}\in {\mathcal {E}}}$, entonces la discrepancia es cero, si todas las aristas tienen cardinalidad par, y uno, si hay una arista de cardinalidad impar.
• El otro extremo está marcado por el hipergrafo completo.${\displaystyle (V,2^{V})}$En este caso la discrepancia es${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$. Cualquier coloración de 2 colores tendrá una clase de color de al menos este tamaño, y este conjunto también es una arista. Por otro lado, cualquier coloración${\displaystyle \chi }$con clases de color de tamaño${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$y${\displaystyle \lfloor {\frac {1}{2}}|V|\rfloor }$demuestra que la discrepancia no es mayor que${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$. Parece que la discrepancia refleja cuán caóticas son las hiperbordes de${\displaystyle {\mathcal {H}}}$Intersecarse. Sin embargo, las cosas no son tan fáciles, como muestra el siguiente ejemplo.
• Colocar${\displaystyle n=4k}$,${\displaystyle k\in {\mathcal {N}}}$y${\displaystyle {\mathcal {H}}_{n}=([n],\{E\subseteq [n]\mid |E\cap [2k]|=|E\setminus [2k]|\})}$En palabras,${\displaystyle {\mathcal {H}}_{n}}$es el hipergrafo con 4k vértices {1,...,4k } , cuyas aristas son todos subconjuntos que tienen el mismo número de elementos en {1,...,2k } que en { 2k +1,...,4k } . Ahora${\displaystyle {\mathcal {H}}_{n}}$tiene muchos (más de${\displaystyle {\binom {n/2}{n/4}}^{2}=\Theta ({\frac {1}{n}}2^{n})}$) bordes que se intersecan de forma compleja. Sin embargo, su discrepancia es cero, ya que podemos colorear {1,...,2 k } de un color y {2 k +1,...,4 k } de otro color.

El último ejemplo demuestra que no podemos determinar la discrepancia observando un único parámetro, como el número de hiperaristas. Sin embargo, el tamaño del hipergrafo proporciona los primeros límites superiores.

1. Para cualquier hipergrafo ${\displaystyle {\mathcal {H}}}$con n vértices y m aristas:

• ${\displaystyle \operatorname {disco} ({\mathcal {H}})\leq {\sqrt {2n\ln(2m)}}.}$

La demostración es una aplicación simple del método probabilístico . Sea${\displaystyle \chi :V\rightarrow \{-1,1\}}$ser una coloración aleatoria, es decir tenemos

${\displaystyle \Pr(\chi (v)=-1)=\Pr(\chi (v)=1)={\frac {1}{2}}}$

de forma independiente para todos${\displaystyle v\in V}$. Desde${\displaystyle \chi (E)=\sum _ {v\in E}\chi (v)}$es una suma de variables aleatorias independientes −1, 1. Entonces tenemos${\displaystyle \Pr(|\chi (E)|>\lambda )<2\exp(-\lambda ^{2}/(2n))}$a pesar de${\displaystyle E\subseteq V}$y${\displaystyle \lambda \geq 0}$. Tomando${\displaystyle \lambda ={\sqrt {2n\ln(2m)}}}$da

${\displaystyle \Pr(\operatorname {disc} ({\mathcal {H}},\chi )>\lambda )\leq \sum _{E\in {\mathcal {E}}}\Pr(|\chi (E)|>\lambda )<1.}$

Dado que una coloración aleatoria con probabilidad positiva tiene discrepancia como máximo${\displaystyle \lambda }$, en particular, hay colores que tienen discrepancias como máximo${\displaystyle \lambda }$. Por eso${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq \lambda .\ \Box }$

2. Para cualquier hipergrafo ${\displaystyle {\mathcal {H}}}$con n vértices y m aristas tales que${\displaystyle m\geq n}$:

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\in O({\sqrt {n}}).}$

Para demostrar esto, fue necesario un enfoque mucho más sofisticado que utilizara la función de entropía. Por supuesto, esto es particularmente interesante para${\displaystyle m=O(n)}$En el caso${\displaystyle m=n}$,${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 6{\sqrt {n}}}$Esto se puede demostrar para valores de n suficientemente grandes. Por lo tanto, este resultado se conoce comúnmente como «Seis desviaciones estándar son suficientes». Se considera uno de los hitos de la teoría de la discrepancia. El método de la entropía ha tenido numerosas aplicaciones, por ejemplo, en la demostración de la cota superior ajustada para las progresiones aritméticas de Matoušek y Spencer ^{[ 6 ]} o la cota superior en términos de la función de fragmentación primal debida a Matoušek ^{[ 7 ] .}

Se pueden alcanzar mejores límites de discrepancia cuando el hipergrafo tiene un grado acotado , es decir, cada vértice de${\displaystyle {\mathcal {H}}}$está contenido en como máximo t aristas, para algún t pequeño . En particular:

• Beck y Fiala ^{[ 8 ]} demostraron que${\displaystyle \operatorname {disc} ({\mathcal {H}})<2t}$; esto se conoce como el teorema de Beck-Fiala . Conjeturaron que${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t}})}$.
• Bednarchak y Helm ^{[ 9 ]} y Helm ^{[ 10 ]} mejoraron la cota de Beck-Fiala en pequeños pasos para${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 2t-3}$(para una situación ligeramente restringida, es decir${\displaystyle t\geq 3}$).
• Bukh ^{[ 11 ]} mejoró esto en 2016 a${\displaystyle 2t-\log ^{*}t}$, dónde${\displaystyle \log ^{*}t}$denota el logaritmo iterado .
• Un corolario del artículo de Beck ^{[ 1 ]} –la primera vez que apareció explícitamente la noción de discrepancia– muestra${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq C{\sqrt {t\log m}}\log n}$para alguna constante C.
• La última mejora en esta dirección se debe a Banaszczyk: ^{[ 12 ]}${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t\log n}})}$.

Es posible obtener mejores límites para la discrepancia en hipergrafos con una estructura especial, como por ejemplo:

• Discrepancia de permutaciones : cuando los vértices son los enteros 1,..., n , y las hiperaristas son todos los intervalos de algunas m permutaciones dadas sobre los enteros.
• Discrepancia geométrica : cuando los vértices son puntos en un espacio euclidiano y las hiperaristas son objetos geométricos, como rectángulos o semiplanos.

• Progresiones aritméticas (Roth, Sárközy, Beck , Matoušek & Spencer )
• Seis desviaciones estándar son suficientes (Spencer)

• Conjetura de Komlós ^{[ 13 ]}

• Integración numérica: métodos de Monte Carlo en altas dimensiones.
• Geometría Computacional: Algoritmos de divide y vencerás .
• Procesamiento de imágenes: Tramado de tonos

• Beck, József ; Chen, William WL (2009). Irregularidades de la distribución . Cambridge University Press. ISBN 978-0-521-09300-2.
• Chazelle, Bernard (2000). El método de la discrepancia: aleatoriedad y complejidad . Cambridge University Press. ISBN 0-521-77093-9.
• Doerr, Benjamin (2005). Aproximación integral (PDF) ( Tesis de habilitación ). Universidad de Kiel . OCLC 255383176. Recuperado el 20 de octubre de 2019 . 
• Matoušek, Jiří (1999). Discrepancia geométrica: una guía ilustrada . Saltador. ISBN 3-540-65528-X.