Twierdzenie o hipergrafie symetrycznym

Twierdzenie o hipergrafie symetrycznym jest twierdzeniem w kombinatoryce , które nakłada górną granicę na liczbę chromatyczną wykresu (lub ogólnie hipergrafu ). Oryginalne odniesienie do tego artykułu jest obecnie nieznane i zostało nazwane folklorem .

Oświadczenie

Grupa działająca na zbiorze $nazywana$ jest przechodnią , jeśli biorąc pod uwagę dowolne dwa elementy $displaystyle$ y $y}$ w $S$ displaystyle $S}$ istnieje sol {\ displaystyle element ${\ Displaystyle f}$ z ${\ Displaystyle G}$ taki, że ${\ Displaystyle f (x) = y}$ . Graf (lub hipergraf) nazywamy symetrycznym , jeśli jego grupa automorfizmów jest przechodnia.

Twierdzenie. Niech ${\ Displaystyle H = (S, E)}$ będzie hipergrafem symetrycznym. Niech ${\ Displaystyle m = | S |}$$\ alpha (H. )}$ niech oznaczają liczbę chromatyczną ${\ Displaystyle H}$$i$ niech liczbę niezależności H ${\ Displaystyle H}$ . Następnie

$${\ Displaystyle \ chi (H) \ równoważnik 1 + {\ Frac {\ ln {m}}} {- \ ln { (1-\alfa (H)/m)}}}}$$

Aplikacje

Twierdzenie to ma zastosowanie w teorii Ramseya , w szczególności w teorii wykresów Ramseya. Korzystając z tego twierdzenia, można pokazać związek między liczbami Ramseya na wykresie a liczbami ekstremalnymi (szczegóły w Graham-Rothschild-Spencer).

Zobacz też

• Teoria Ramseya