On cross-intersecting families (Q1201261)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On cross-intersecting families
scientific article

    Statements

    On cross-intersecting families (English)
    0 references
    17 January 1993
    0 references
    Sharpening a result of \textit{A. Sali} [An Erdős-Ko-Rado theorem for posets, preprint] the following result is proved. Suppose that \(1\leq t\leq s\leq n\), \(X\) is an \(n\)-element set, \({\mathcal F}\), \({\mathcal G}\) are families of subsets of \(X\), if \(F\in{\mathcal F}\), \(G\in{\mathcal G}\) then \(| F\cap G|\geq t\), and finally, \(|{\mathcal G}|\leq|{\mathcal F}|\leq|{\mathcal F}(n,t)|\) holds where, if \(n+t\) is even, \({\mathcal F}(n,t)=\{F\subseteq X:| F|\geq(n+t)/2\}\), and if \(n+t\) is odd and \(x\in X\) is some element, then \({\mathcal F}(n,t)=\{F\subseteq X:| F\cap(X-\{x\})|\geq(n-1+t)/2\}\). Then, \(|{\mathcal F}|+|{\mathcal G}|\leq|{\mathcal F}(n,t)|+|{\mathcal F}(n,2s-t)|\).
    0 references
    cross-intersecting families
    0 references
    Katona's theorem
    0 references
    Erdős-Ko-Rado theorem
    0 references
    0 references

    Identifiers