Finding a set of pairs that "cover" all combinations of a larger set Sorry for the probably-confusing title but I'm not too familiar with this area and don't know the right terminology. That makes searching for solutions hard too.
The problem is relatively simple: suppose I have a set of size $n$, called $S$. I then consider the set $X$ which is all subsets of $S$ of size $m$ (so that there are $n \choose m$ of these). I wish to find a minimal set of pairs, $Y$, such that that every set in $X$ contains at least one pair from $Y$.
For example, if $S = \{1,2,3,4,5\}$ and $m = 3$, then
$$X = \{\{1,2,3\}, \{1,3,4\}, \{1,3,5\}, \{1,3,4\}, \{1,3,5\},\{1,4,5\},\{2,3,4\}, \{2,3,5\}, \{2,4,5\}, \{3,4,5\}\}$$
and then a possible minimal $Y$ would be $\{\{1,2\}, \{2,3\}, \{1,3\},\{4,5\}\}$.
I'm looking for a way to generate a set $Y$ given $n$ and $m$ (where $S = \{1,2,\dots, n\}$) or even a set $Z$ which satisfies the criteria for $Y$ but isn't minimal but reasonably close in size. My end goal is to run a somewhat expensive algorithm based on $Y$ or $Z$ which is why the size matters. I could of course choose $Z$ to be all pairs but thats $n \choose 2$ and much too big.
So far, I've written some code that can do this but in a naive way: calculate $X$, greedily pick a point to add to $Y$, remove the covered sets from $X$, and repeat. But this is expensive  - even just generating $X$ can be slow. 
Thanks for any help.
 A: It can help to rephrase your problem in terms of graph theory. Here, you can think of the numbers from $1$ to $n$ as nodes, and each pair of numbers as an edge connecting two nodes. What you're asking for, then, is the smallest number of edges you have to remove from a complete graph on $n$ vertices so that the resulting graph does not contain any clique of size $m$. 
The answer to this problem is given by Turan's theorem. In particular, you need to remove at least $(m-1)\binom{n/(m-1)}{2} \approx \frac{n^2}{2(m-1)}$ edges, so that the resulting graph is a complete $(m-1)$-partite graph. 
In the language of pairs, we first split $S$ as evenly as possible into $m-1$ subsets $S_1, S_2, \dots, S_{m-1}$ (so each $S_i$ has size either $\lfloor \frac{n}{m-1}\rfloor$ or $\lceil\frac{n}{m-1}\rceil$). Our set of pairs $Y$ is then the set of all pairs $\{a, b\}$ where $a$ and $b$ come from the same subset $S_i$. Since any set of $m$ elements must contain two elements from the same subset (by the pigeonhole principle), any set of $m$ elements contains at least one pair from $Y$ (and Turan's theorem shows that this is in fact as good as you can do).
