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