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
      0 references
      0 references
      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
      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

      Identifiers