Erdős-Ko-Rado theorem for a restricted universe (Q2185207)

From MaRDI portal
Revision as of 11:11, 1 August 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Erdős-Ko-Rado theorem for a restricted universe
scientific article

    Statements

    Erdős-Ko-Rado theorem for a restricted universe (English)
    0 references
    0 references
    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
    0 references
    restricted universe
    0 references
    intersecting family of subsets
    0 references