Stability analysis for \(k\)-wise intersecting families

Vikram Kamat

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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.

Détail

DOI : 10.37236/602

Classification : 05D05
Mots-clés : intersection theorems, stability