Stability Analysis for $k$-wise Intersecting Families

  • Vikram Kamat

Abstract

We consider the following generalization of the seminal Erdős–Ko–Rado theorem, due to Frankl. For some $k\geq 2$, let $\mathcal{F}$ be a $k$-wise intersecting family of $r$-subsets of an $n$ element set $X$, i.e. for any $F_1,\ldots,F_k\in \mathcal{F}$, $\cap_{i=1}^k F_i\neq \emptyset$. If $r\leq \dfrac{(k-1)n}{k}$, then $|\mathcal{F}|\leq {n-1 \choose r-1}$. We prove a stability version of this theorem, analogous to similar results of Dinur-Friedgut, Keevash-Mubayi and others for the EKR theorem. The technique we use is a generalization of Katona's circle method, initially employed by Keevash, which uses expansion properties of a particular Cayley graph of the symmetric group.

Published
2011-05-16
Article Number
P115