Simetrik hipergraf teoremi - Symmetric hypergraph theorem

Simetrik hipergraf teoremi teorem kombinatorik bir üst sınır koyan kromatik sayı bir grafik (veya hiper grafik Genel olarak). Bu makalenin orijinal referansı şu anda bilinmiyor ve folklor.^[1]

Beyan

Bir grup ${displaystyle G}$ bir sette hareket etmek ${displaystyle S}$ denir geçişli herhangi iki öğe verilirse ${displaystyle x}$ ve ${displaystyle y}$ içinde ${displaystyle S}$bir eleman var ${displaystyle f}$ nın-nin ${displaystyle G}$ öyle ki ${displaystyle f (x) = y}$. Bir grafik (veya hiper grafik) denir simetrik eğer onun otomorfizm grubu geçişlidir.

Teorem. İzin Vermek ${displaystyle H = (S, E)}$ simetrik bir hipergraf olabilir. İzin Vermek ${displaystyle m = | S |}$ve izin ver ${displaystyle chi (H)}$ kromatik sayısını gösterir ${displaystyle H}$ve izin ver ${displaystyle alpha (H)}$ belirtmek bağımsızlık numarası nın-nin ${displaystyle H}$. Sonra

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

Başvurular

Bu teoremin uygulamaları vardır Ramsey teorisi özellikle grafik Ramsey teorisi. Bu teoremi kullanarak, grafik Ramsey sayıları ile uç sayılar arasındaki ilişki gösterilebilir (ayrıntılar için Graham-Rothschild-Spencer'a bakınız).

Ayrıca bakınız

• Ramsey teorisi

Notlar