Teorema del hipergrafo simétrico

El teorema del hipergrafo simétrico es un teorema de combinatoria que establece una cota superior para el número cromático de un grafo (o hipergrafo en general). La referencia original de este artículo se desconoce por el momento y se ha denominado folclore . ^{[ 1 ]}

Un grupo${\displaystyle G}$actuando en un plató${\displaystyle S}$Se denomina transitivo si, dados dos elementos cualesquiera,${\displaystyle x}$y${\displaystyle y}$en${\displaystyle S}$, existe un elemento${\displaystyle f}$de${\displaystyle G}$de tal manera que${\displaystyle f(x)=y}$Un grafo (o hipergrafo) se denomina simétrico si su grupo de automorfismos es transitivo.

Teorema. Sea${\displaystyle H=(S,E)}$Sea un hipergrafo simétrico.${\displaystyle m=|S|}$y dejar${\displaystyle \chi (H)}$denotan el número cromático de${\displaystyle H}$y dejar${\displaystyle \alpha (H)}$denota el número de independencia de${\displaystyle H}$. Entonces

$${\displaystyle \chi (H)\leq 1+{\frac {\ln {m}}{-\ln {(1-\alpha (H)/m)}}}}$$

Este teorema tiene aplicaciones en la teoría de Ramsey , específicamente en la teoría de Ramsey de grafos . Mediante este teorema, se puede demostrar una relación entre los números de Ramsey de grafos y los números extremales (véase Graham-Rothschild-Spencer para más detalles).

El teorema también se ha aplicado a problemas que involucran progresiones aritméticas. Por ejemplo, sea${\displaystyle r_{k}(n)}$denotan el número mínimo de colores necesarios para que exista un${\displaystyle r_{k}(n)}$-coloración de${\displaystyle [1,n]}$que evita cualquier monocromático${\displaystyle k}$progresión aritmética de -términos . El teorema del hipergrafo simétrico se puede utilizar para demostrar que ^{[ 2 ]}

${\displaystyle r_{k}(n)<{\frac {2n\log n}{\log \log n}}(1+o(1))}$

• teoría de Ramsey
• Teorema de Van der Waerden