Erdős--Ko--Rado for three sets (Q2368657)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Erdős--Ko--Rado for three sets |
scientific article |
Statements
Erdős--Ko--Rado for three sets (English)
0 references
28 April 2006
0 references
Let \(k\leq s\leq 3\dot{k}.\) Then \(f(n,k,s)\) denotes the maximum size of family \(\mathcal{F}\subset [ n]^{k\text{ }}\) so that if \(A,B,C\in \mathcal{F}\) satisfy \(\left| A\cup B\cup C\right| \leq s,\) then \( A\cap B\cap C\neq \emptyset .\) The function \(f\) has been introduced by Katona. \textit{P. Frankl} and \textit{Z. Fueredi} [Combinatorica 3, 341--349 (1983; Zbl 0529.05001)] proved that, if \(2k\leq s\leq 3\dot{k},\) and \(n\geq k^{2}+3k,\) then \(f(n,k,s)= \binom{n-1}{k-1}.\) In the paper it is shown that for \(k\geq 3\) and \(n\geq 3k/2\) we have \(f(n,k,2k)=\binom{n-1}{k-1}\) which answers in the affirmative a conjecture by Frankl and Fueredi.
0 references
set systems
0 references
nontrivial family
0 references
Erdős-Ko-Rado
0 references