Uniform Intersecting Families with Covering Number Restrictions (Q4383736)
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 1138604
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Uniform Intersecting Families with Covering Number Restrictions |
scientific article; zbMATH DE number 1138604 |
Statements
Uniform Intersecting Families with Covering Number Restrictions (English)
0 references
27 July 1998
0 references
covering number
0 references
intersecting family
0 references
covering restriction
0 references
extremal set
0 references
cover
0 references
0.9082860946655272
0 references
0.897075355052948
0 references
0.8951717019081116
0 references
0.8708977103233337
0 references
0.8647502064704895
0 references
Let \(X\) be a finite set and \({X\choose k}\) the family of all \(k\)-element subsets of \(X\). A family \({\mathcal F} \subseteq {X\choose k}\) is called intersecting if \(F\cap G\neq \varnothing\) holds for all \(F,G\in {\mathcal F}\). A set \(C\subseteq X\) is said to be a cover of \({\mathcal F}\) if \(C\cap F\neq \varnothing\) holds for all \(F\in {\mathcal F}\). Let \(\tau ({\mathcal F})\) be the minimum cardinality of any cover of \({\mathcal F}\). For \({\mathcal F} \subseteq {X\choose k}\) and any integer \(t\geq 1\) let \(C_t({\mathcal F})\) be the family of all covers of \({\mathcal F}\) of size \(t\) and \[ p_t (k)= \max\biggl\{ \bigl| C_t ({\mathcal F}) \bigr|: {\mathcal F} \subseteq {X\choose k} \text{ is intersecting and }\tau ({\mathcal F}) =t\biggr\}. \] It is proved that \(p_t(k)= k^t-b(t) k^{t-1}+ O(k^{t-2})\), where \(b(t)\) is a well-defined function such that (i) \({t\choose 2}\geq b(t)\geq {1\over\sqrt 2} \left \lfloor {t-1 \over 2} \right \rfloor^{3/2}\), and (ii) \(b(t)= {t\choose 2}\) if \(t\in\{4,5\}\).
0 references