Skip to main content
MathOverflow

Return to Question

added 108 characters in body
Source Link
Lev Reyzin
Lev Reyzin
  • 175
  • 1
  • 6

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$.

Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?

I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r << s << n$. I am more worried about asymptotic behavior than exact bounds.

This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.

EDIT: Thanks to @Gerhard, I see this is a well known problem called covering numbers / covering designs.

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$.

Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?

I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r << s << n$. I am more worried about asymptotic behavior than exact bounds.

This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$.

Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?

I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r << s << n$. I am more worried about asymptotic behavior than exact bounds.

This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.

EDIT: Thanks to @Gerhard, I see this is a well known problem called covering numbers / covering designs.

Source Link
Lev Reyzin
Lev Reyzin
  • 175
  • 1
  • 6

A small collection of large subsets covering all small subsets.

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$.

Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?

I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r << s << n$. I am more worried about asymptotic behavior than exact bounds.

This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.