Erdős-Ko-Rado theorem for a restricted universe (Q2185207)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Erdős-Ko-Rado theorem for a restricted universe |
scientific article; zbMATH DE number 7208416
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Erdős-Ko-Rado theorem for a restricted universe |
scientific article; zbMATH DE number 7208416 |
Statements
Erdős-Ko-Rado theorem for a restricted universe (English)
0 references
4 June 2020
0 references
Summary: A family \(\mathcal F\) of \(k\)-element subsets of the \(n\)-element set \([n]\) is called intersecting if \(F \cap F^\prime\neq \emptyset\) for all \(F, F^\prime \in \mathcal F\). \textit{P. Erdős} et al. [Q. J. Math., Oxf. II. Ser. 12, 313--320 (1961; Zbl 0100.01902)] showed that \(|\mathcal F| \leq\binom{n - 1}{k - 1}\) if \(n \geq 2k\). Since then a large number of results providing best possible upper bounds on \(|\mathcal F|\) under further restraints were proved. The paper of \textit{W.-T. Li} et al. [Electron. J. Comb. 20, No. 3, Research Paper P38, 11 p. (2013; Zbl 1295.05250)] is one of them. We consider the restricted universe \(\mathcal W = \left\{F \in\binom{[n]}{k}: |F \cap [m]| \geq \ell \right\}, n \geq 2k, m \geq 2\ell\) and determine \(\max |\mathcal F|\) for intersecting families \(\mathcal F \subset \mathcal W\). Then we use this result to solve completely the problem considered by Li et al. [loc. cit.].
0 references
restricted universe
0 references
intersecting family of subsets
0 references
0.8613215684890747
0 references
0.8583623170852661
0 references
0.8507131934165955
0 references
0.848028838634491
0 references
0.8410207033157349
0 references