On the treewidth of generalized q-Kneser graphs

Klaus Metsch

paper

On the treewidth of generalized q-Kneser graphs

arXiv:2405.11584

Abstract

The generalized $q$ -Kneser graph $K_{q} (n, k, t)$ for integers $k > t > 0$ and $n > 2 k - t$ is the graph whose vertices are the $k$ -dimensional subspaces of an $n$ -dimensional $F_{q}$ -vectorspace with two vertices $U_{1}$ and $U_{2}$ adjacent if and only if $dim (U_{1} \cap U_{2}) < t$ . We determine the treewidth of the generalized $q$ -Kneser graphs $K_{q} (n, k, t)$ when $t \geq 2$ and $n$ is sufficiently large compared to $k$ . The imposed bound on $n$ is a significant improvement of the previously known bound. One consequence of our results is that the treewidth of each $q$ -Kneser graph $K_{q} (n, k, t)$ with $k > t > 0$ and $n \geq 3 k - t + 9$ is equal to $\gauss{n}{k}-\gauss{n-t}{k-t}-1$.