Combinatorial Theory

For integers \(n \geq k \geq 1\), the Kneser graph \(K(n, k)\) is the graph with vertex-set consisting of all the \(k\)-element subsets of \(\{1,2,\ldots,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 › 10000 k s^5\) and \(\mathcal F\) is set of vertices of \(K(n,k)\) of size larger than \[\{A \subset \{1,2,\ldots,n\}: |A|=k, A \cap \{1,2,\ldots,s\} \neq \varnothing\},\] then the subgraph of \(K(n,k)\) induced by \(\mathcal F\) has maximum degree at least \[ \left(1 - O\left(\sqrt{s^3 k/n}\right)\right)\frac{s}{s+1} \cdot {n-k \choose k} \cdot \frac{\left|{\mathcal F}\right|}{\binom{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, \ldots, s\). An appealing special case of the above result is that if \(\mathcal{F}\) is a family of \(k\)-element subsets of \(\{1,2,\ldots,n\}\) with \(|\mathcal{F}| = {n-1 \choose k-1}+1\), then there exists \(A \in \mathcal{F}\) such that \(\mathcal{F}\) is disjoint from at least \[\left(1/2-O\left(\sqrt{k/n}\right)\right){n-k-1 \choose 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