Random Kneser Graphs and Hypergraphs

Electronic Journal Of Combinatorics

Andrey Kupavskii¹ 

关键词: Random Kneser graphs;    Chromatic number;    Transference;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

The Kneser graph $KG_{n,k}$ is the graph whose vertices are the $k$-element subsets of $[n],$ with two vertices adjacent if and only if the corresponding sets are disjoint. A famous result due to Lovász states that the chromatic number of $KG_{n,k}$ is eq

【 授权许可】

Others