Symetrická věta o hypergrafu - Symmetric hypergraph theorem

The Symetrická věta o hypergrafu je věta v kombinatorika která klade horní mez na chromatické číslo a graf (nebo hypergraf obecně). Původní reference pro tento dokument není v tuto chvíli známa a byla vyvolána folklór.^[1]

Prohlášení

A skupina ${displaystyle G}$ působící na scénu ${displaystyle S}$ je nazýván tranzitivní pokud jsou dány nějaké dva prvky ${displaystyle x}$ a ${displaystyle y}$ v ${displaystyle S}$, existuje prvek ${displaystyle f}$ z ${displaystyle G}$ takhle ${displaystyle f (x) = y}$. Nazývá se graf (nebo hypergraf) symetrický Pokud je to automorfická skupina je tranzitivní.

Teorém. Nechat ${displaystyle H = (S, E)}$ být symetrický hypergraf. Nechat ${displaystyle m = | S |}$a nechte ${displaystyle chi (H)}$ označit chromatický počet ${displaystyle H}$a nechte ${displaystyle alfa (H)}$ označit číslo nezávislosti z ${displaystyle H}$. Pak

${displaystyle chi (H) <1+ {frac {m} {alpha (H)}} v m.}$

Aplikace

Tato věta má aplikace pro Ramseyova teorie konkrétně graf Ramseyova teorie. Pomocí této věty lze ukázat vztah mezi grafem Ramseyových čísel a extrémními čísly (podrobnosti viz Graham-Rothschild-Spencer).

Viz také

• Ramseyova teorie

Poznámky