Teorema del hipergrafo simétrico

El teorema del hipergrafo simétrico es un teorema de combinatoria que establece un límite 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]

Declaración

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

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

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

Aplicaciones

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

Véase también

• Teoría de Ramsey

Notas

1. R. Graham, B. Rothschild, J. Spencer. Teoría de Ramsey. 2.ª ed., Wiley, Nueva York, 1990.