Discrepancia de hipergrafías

---

En la configuración clásica, nuestro objetivo es dividir los vértices de una hipergrafía 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 −1 y +1 colores . Las clases de color y forman la partición correspondiente. Para un hiperborde , establezca${\displaystyle {\mathcal {H}}=(V,{\mathcal {E}})}$${\displaystyle \chi \colon V\rightarrow \{-1,+1\}}$${\ estilo de visualización \ chi ^ {-1} (-1)}$${\ estilo de visualización \ chi ^ {-1} (+1)}$${\displaystyle E\in {\mathcal {E}}}$

La discrepancia de con respecto a${\displaystyle {\mathcal {H}}}$${\ estilo de visualización \ chi}$ y la discrepancia de${\displaystyle {\mathcal {H}}}$ están definidas por

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 (descritos en la p. 39). ^[5] En ese momento, los problemas de discrepancia se llamaban cuasi- problemas de Ramsey .

El último ejemplo muestra que no podemos esperar determinar la discrepancia observando un solo parámetro como el número de hiperbordes. Aún así, el tamaño de la hipergrafía produce los primeros límites superiores.

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

La demostración es una simple aplicación del método probabilístico: Sea un color aleatorio, es decir, tenemos${\ estilo de visualización \ chi: V \ flecha derecha \ {-1,1 \}}$

---