Stability analysis for \(k\)-wise intersecting families (Q540125): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Importer (talk | contribs)
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
    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

    Identifiers