No label defined (Q3679189)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3900758
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3900758 |
Statements
1984
0 references
Sperner theory
0 references
extremal set theory
0 references
Erdős-Ko-Rado-Theorem
0 references
0.8790619373321533
0 references
0.8719151616096497
0 references
0.8691734671592712
0 references
0.8665931820869446
0 references
[For the entire collection see Zbl 0559.00001.] The main result is Theorem 3: Let \(\mu\geq 6\), \(\nu\geq 6\), and k be integers and let R be a finite set, \(| R| =r\geq k\). If \({\mathcal F}\leq \left( \begin{matrix} R\\ k\end{matrix} \right)\), (1) \((r-1/\nu)+1\leq k\leq (\mu -1/\mu)(r-1)\), and \({\mathcal F}\) satisfies (2) \(X_ 1\cap X_ 2\cap...\cap X_{\mu}\neq \emptyset\) for all \(X_ 1,X_ 2,...,X_{\mu}\in {\mathcal F}\), as well as (3) \(X_ 1\cup X_ 2\cup...\cup X_{\nu}\neq R\) for all \(X_ 1,X_ 2,...,X_{\nu}\in {\mathcal F}\), then \({\mathcal F}\leq \left( \begin{matrix} r-2\\ k-1\end{matrix} \right)\). This is best possible. The only maximal families are \({\mathcal F}=\{X\in \left( \begin{matrix} R\\ k\end{matrix} \right):x\in X,y\not\in X\}\) for two fixed elements x,y\(\in R\), \(x\neq y\). The condition (1) is natural; otherwise (2) or (3) is satisfied automatically. This result is related to \textit{P. Frankl}'s generalization (\({\mathcal F}\) satisfies (2) only) [J. Comb. Theory, Ser. A 20, 1-11 (1976; Zbl 0328.05002)] of the wellknown Erdős- Ko-Rado-Theorem. Recently \textit{K. Engel} and the author proved the theorem also for \(\mu\),\(\nu\geq 4\) [Acta Cybern. 7 (to appear in 1986)]. It remains the conjecture that the theorem is also true for \(\mu =2,\nu \geq 3\) or \(\mu\geq 3,\nu \geq 2\).
0 references