Maximal degrees in subgraphs of Kneser graphs

Abstract

In this paper, we study the maximum degree in non-empty induced subgraphs of the Kneser graph $KG(n,k)$. One of the main results asserts that, for $k>k_0$ and $n>64k^2$, whenever a non-empty subgraph has $m\ge k\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)$ vertices, its maximum degree is at least $\frac{1}{2}(1-\frac{k^2}{n})m-\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)\ge 0.49m$. This bound is essentially best possible. One of the intermediate steps is to obtain structural results on non-empty subgraphs with small maximum degree.

References in corpus (1)

• Structure and Supersaturation for Intersecting Families