Stability analysis for \(k\)-wise intersecting families (Q540125): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1009.3973 / rank | |||
Normal rank |
Latest revision as of 15:09, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Stability analysis for \(k\)-wise intersecting families |
scientific article |
Statements
Stability analysis for \(k\)-wise intersecting families (English)
0 references
1 June 2011
0 references
Summary: We consider the following generalization of the seminal Erdős-Ko-Rado theorem, due to \textit{Frankl} [``On Sperner families satisfying an additional condition,'' J. Comb. Theory, Ser. A 20, 111 (1976; Zbl 0328.05002)]. 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,\dots, F_k\in{\mathcal F}\), \(\bigcap^k_{i=1} F_i\neq \emptyset\). If \(r\leq {(k-1)n\over 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 [\textit{I. Dinur} and \textit{E. Friedgut}, ``Intersecting families are essentially contained in juntas,'' Comb. Probab. Comput. 18, No.\,1-2, 107--122 (2009; Zbl 1243.05235)], Keevash-Mubayi [\textit{P. Keevash} and \textit{D. Mubayi}, ``Set systems without a simplex or a cluster,'' Combinatorica 30, No.\,2, 175--200 (2010; Zbl 1224.05249)] 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.
0 references
intersection theorems
0 references
stability
0 references