Stability results for vertex Turán problems in Kneser graphs (Q2415074)

Summary: The vertex set of the Kneser graph \(K(n,k)\) is \(V = \binom{[n]}{k}\) and two vertices are adjacent if the corresponding sets are disjoint. For any graph \(F\), the largest size of a vertex set \(U \subseteq V\) such that \(K(n,k)[U]\) is \(F\)-free, was recently determined by \textit{M. Alishahi} and \textit{A. Taherkhani} [J. Comb. Theory, Ser. A 159, 269--282 (2018; Zbl 1392.05108)], whenever \(n\) is large enough compared to \(k\) and \(F\). In this paper, we determine the second largest size of a vertex set \(W \subseteq V\) such that \(K(n,k)[W]\) is \(F\)-free, in the case when \(F\) is an even cycle or a complete multi-partite graph. In the latter case, we actually give a more general theorem depending on the chromatic number of \(F\).