Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem (Q405143): Difference between revisions

Summary: Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser\((n,k)\) is the graph with vertex set \(\binom{[n]}{k}\), such that two vertices are adjacent if they are disjoint. We determine, for large values of \(n\) with respect to \(k\), the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-Ko-Rado theorem (for large \(n\) with respect to \(k\)) when a number of disjoint pairs of \(k\)-sets are allowed.