# Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem

Keywords:
graph theory, Kneser graph, treewidth, separators, Erdős-Ko-Rado

### Abstract

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.