For integers $n\ge k\ge 1$, the Kneser graph $K(n,k)$ is the graph with vertex-set consisting of all the $k$-element subsets of $\{1,2,\dots ,n\}$, where two $k$-element sets are adjacent in $K(n,k)$ if they are disjoint. We show that if $(n,k,s)\in {\mathbb{N}}^3$ with $n›10000k{s}^5$ and $\mathcal{F}$ is set of vertices of $K(n,k)$ of size larger than $$\{A\subset \{1,2,\dots ,n\}:|A|=k,A\cap \{1,2,\dots ,s\}\ne \varnothing \},$$ then the subgraph of $K(n,k)$ induced by $\mathcal{F}$ has maximum degree at least $$(1-O\left(\sqrt{s^{3}k/n}\right))\frac{s}{s+1}\cdot (\genfrac{}{}{0ex}{}{n-k}{k})\cdot \frac{\left|\mathcal{F}\right|}{(\genfrac{}{}{0ex}{}{n}{k})}.$$ This is sharp up to the behaviour of the error term $O(\sqrt{s^{3}k/n})$. In particular, if the triple of integers $(n,k,s)$ satisfies the condition above, then the minimum maximum degree does not increase `continuously' with $\left|\mathcal{F}\right|$. Instead, it has $s$ jumps, one at each time when $\left|\mathcal{F}\right|$ becomes just larger than the union of $i$ stars, for $i=1,2,\dots ,s$. An appealing special case of the above result is that if $\mathcal{F}$ is a family of $k$-element subsets of $\{1,2,\dots ,n\}$ with $|\mathcal{F}|=(\genfrac{}{}{0ex}{}{n-1}{k-1})+1$, then there exists $A\in \mathcal{F}$ such that $\mathcal{F}$ is disjoint from at least $$(1/2-O\left(\sqrt{k/n}\right))(\genfrac{}{}{0ex}{}{n-k-1}{k-1})$$ of the other sets in $\mathcal{F}$; we give both a random and a deterministic construction showing that this is asymptotically sharp if $k=o(n)$. In addition, it solves (up to a constant multiplicative factor) a problem of Gerbner, Lemons, Palmer, Patkós and Szécsi.

Frankl and Kupavskii, using different methods, have recently proven similar results under the hypothesis that $n$ is at least a quadratic in $k$.

Mathematics Subject Classifications: 05D05

Keywords: Kneser, intersecting, sensitivity, Erdős-Ko-Rado type theorem