How many sets of size 𝑋 are needed to assure that every set of K elements is a subset of (at least) one of these sets (where K ≪ X &lt; N). And also, how can these sets be chosen to obtain this minimum?In particular, the sizes that interest me are: N = O ( 2 n c 1 ) , X = O ( 2 n ) , K = O ( n c 2 ) , where n is a variable, c 1 and c 2 are constants.

Question

How many sets of size 𝑋 are needed to assure that every set of K elements is a subset of (at least) one of these sets (where   K  ≪  X  &amp;lt;  N). And also, how can these sets be chosen to obtain this minimum?In particular, the sizes that interest me are:                    N                            =        O        (                  2                                    n                                                c                  1                                                                    )        ,                            X                            =        O        (                  2          n                )        ,                            K                            =        O        (                  n                                    c              2                                      )        ,            where   n is a variable,       c    1   and       c    2   are constants.

Adrienne Harper · Accepted Answer

What you are asking about are called covering designs. A more standard notation in combinatorics defines (𝑣,𝑘,𝑡)-covering design to mean:  v  = total number of points (your universe   N)  k  = size of subsets (blocksize, your set size   X)  t  = size of covered combinations (your   K elements)There is a special case where each   t-subset is covered exactly once, and these are known as Steiner systems. Obviously in those cases the number of blocks used is a minimum.The minimum number of blocks (  k-subsets) needed to cover all   t-subsets of a &quot;universe&quot; of size   v is termed   C  (  v  ,  k  ,  t  ), and there is no general formula for it. In fact not much is known for values of 𝑡 more than ten.There is a well-known general lower bound for   C  (  v  ,  k  ,  t  ) called the Schönheim inequality:  C  (  v  ,  k  ,  t  )  ≥  ⌈  (  v      /    k  )  ∗  C  (  v  −  1  ,  k  −  1  ,  t  −  1  )  ⌉which can be applied recursively down to the case   t  =  1, where trivially:  C  (  v  ,  k  ,  1  )  =  ⌈  v      /    k  ⌉

Jamar Hays · Accepted Answer

Are covering numbers what you had in mind? Their (v,k,t) corresponds to your (N,X,K), if I&#039;m not mistaken. Generally these covering numbers are very hard to compute, even for moderate values of (N,X,K). But perhaps asymptotic results are known that would help with the particular very large sizes that interest you.

How many sets of size 𝑋 are needed to assure that every set of K elements is a subset of (at least) one of these sets (where K<X<N). And also, how can these sets be chosen to obtain this minimum?

Answered question

Answer & Explanation

New Questions in Precalculus