Discrepancia de hipergrafos

Área de la teoría de la discrepancia

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

Definiciones

En el contexto clásico, nuestro objetivo es dividir los vértices de un hipergrafo 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 se puede representar mediante un coloreado . Llamamos colores −1 y +1 . Las clases de color y forman la partición correspondiente. Para una hiperarista , establezca ${\displaystyle {\mathcal {H}}=(V,{\mathcal {E}})}$ ${\displaystyle \chi \colon V\rightarrow \{-1,+1\}}$ ${\displaystyle \chi ^{-1}(-1)}$ ${\displaystyle \chi ^{-1}(+1)}$ ${\displaystyle E\in {\mathcal {E}}}$

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

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

${\displaystyle \operatorname {disc} ({\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] Los resultados anteriores sobre este problema incluyen el famoso límite inferior de la discrepancia de las progresiones aritméticas de Roth ^[2] y los límites 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 llamaban problemas cuasi- Ramsey .

Ejemplos

Para tener una idea intuitiva de este concepto, veamos algunos ejemplos.

• Si todas las aristas de se intersecan de manera trivial, es decir, para dos aristas distintas , entonces la discrepancia es cero, si todas las aristas tienen cardinalidad par, y uno, si hay una arista de cardinalidad impar. ${\displaystyle {\mathcal {H}}}$ ${\displaystyle E_{1}\cap E_{2}=\varnothing }$ ${\displaystyle E_{1},E_{2}\in {\mathcal {E}}}$
• El otro extremo está marcado por el hipergrafo completo . En este caso la discrepancia es . Cualquier coloración 2 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 con clases de color de tamaño y demuestra que la discrepancia no es mayor que . Parece que la discrepancia refleja cuán caóticas se intersecan las hiperaristas de . Sin embargo, las cosas no son tan fáciles, como lo muestra el siguiente ejemplo. ${\displaystyle (V,2^{V})}$ ${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$ ${\displaystyle \chi }$ ${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$ ${\displaystyle \lfloor {\frac {1}{2}}|V|\rfloor }$ ${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$ ${\displaystyle {\mathcal {H}}}$
• Conjunto , y . En palabras, es el hipergrafo sobre 4 k vértices {1,...,4 k }, cuyas aristas son todos subconjuntos que tienen el mismo número de elementos en {1,...,2 k } que en {2 k +1,...,4 k }. Ahora tiene muchas (más de ) aristas que se intersecan de manera complicada. 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. ${\displaystyle n=4k}$ ${\displaystyle k\in {\mathcal {N}}}$ ${\displaystyle {\mathcal {H}}_{n}=([n],\{E\subseteq [n]\mid |E\cap [2k]|=|E\setminus [2k]|\})}$ ${\displaystyle {\mathcal {H}}_{n}}$ ${\displaystyle {\mathcal {H}}_{n}}$ ${\displaystyle {\binom {n/2}{n/4}}^{2}=\Theta ({\frac {1}{n}}2^{n})}$

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

Hipergrafías generales

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

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

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

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

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

${\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 , en particular, hay coloraciones que tienen discrepancia como máximo . Por lo tanto ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq \lambda .\ \Box }$

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

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

Para demostrarlo, fue necesario un enfoque mucho más sofisticado que utiliza la función de entropía. Por supuesto, esto es particularmente interesante para . En el caso , se puede demostrar para n lo suficientemente grande. Por lo tanto, este resultado se conoce generalmente 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 visto muchas otras aplicaciones, por ejemplo, en la prueba del límite superior estricto para las progresiones aritméticas de Matoušek y Spencer ^[6] o el límite superior en términos de la función de fragmentación primaria debido a Matoušek. ^[7] ${\displaystyle m=O(n)}$ ${\displaystyle m=n}$ ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 6{\sqrt {n}}}$

Hipergrafos de grado acotado

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

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

Hipergrafos especiales

Son posibles límites mejores para la discrepancia para hipergrafos con una estructura especial, como:

• Discrepancia de permutaciones : cuando los vértices son los números enteros 1,..., n , y las hiperaristas son todos los intervalos de algunas m permutaciones dadas en los números 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 semiespacios.

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

Grandes problemas abiertos

• Conjetura de Komlós ^[13]

Aplicaciones

• 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: semitonos

Notas

1. J. Beck: "La estimación de Roth de la discrepancia de las secuencias de números enteros es casi precisa", páginas 319-325. Combinatorica , 1, 1981
2. KF Roth: "Observación sobre secuencias de números enteros", páginas 257–260. Acta Aritmética 9, 1964
3. J. Spencer: "Una observación sobre la coloración de números enteros", páginas 43-44. Canadian Mathematical Bulletin 15, 1972.
4. P. Erdős y J. Spencer: "Desequilibrios en coloraciones k", páginas 379–385. Networks 1, 1972.
5. P. Erdős y J. Spencer: "Métodos probabilísticos en combinatoria". Budapest: Akadémiai Kiadó , 1974.
6. J. Matoušek y J. Spencer: "Discrepancia en progresiones aritméticas", páginas 195-204. Journal of the American Mathematical Society 9, 1996.
7. J. Matoušek: "Límite superior estricto para la discrepancia de semiespacios", páginas 593–601. Discrepancia y geometría computacional 13, 1995.
8. J. Beck y T. Fiala: "Teoremas de formación de números enteros", páginas 1–8. Discrete Applied Mathematics 3, 1981.
9. D. Bednarchak y M. Helm: "Una nota sobre el teorema de Beck-Fiala", páginas 147-149. Combinatorica 17, 1997.
10. M. Helm: "Sobre el teorema de Beck-Fiala", página 207. Matemáticas Discretas 207, 1999.
11. B. Bukh: "Una mejora del teorema de Beck-Fiala", págs. 380-398. Combinatoria, probabilidad y computación 25, 2016.
12. Banaszczyk, W. (1998), "Vectores de equilibrio y medida gaussiana de cuerpos convexos n -dimensionales", Random Structures & Algorithms , 12: 351–360, doi :10.1002/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S.
13. Bansal, Nikhil; Dadush, Daniel; Garg, Shashwat (enero de 2019). "Un algoritmo para la conjetura de Komlós que coincide con el límite de Banaszczyk". Revista SIAM de Computación . 48 (2): 534–553. doi :10.1137/17M1126795. ISSN  0097-5397.

Referencias

• 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. Consultado el 20 de octubre de 2019 .
• Matoušek, Jiří (1999). Discrepancia geométrica: una guía ilustrada . Saltador. ISBN 3-540-65528-X.