Collection of subset generating every pairs of elements I'm looking forward to a construction with the following property:
Given a set S of n elements, find a small/the smallest collection of subsets of S of size k such that for every pair of elements a, b in S, there exist a subset containing both a and b.
I'm especially wondering about k = log(n), or k=sqrt(n).
Said otherwise, is there a nice way to get a complete graph on n vertices from the union of cliques on some subsets of vertices of size k ?
If yes, do you know of an algorithm able to find subsets that "cover" an arbitrary graph rather than the complete graph ?
 A: The perfect collection would be a family of $k$-subsets of $S$ such that every pair $\{a,b\} \subseteq S$ is contained in exactly one $k$-subset. This family will consist of $\binom n2/\binom k2$ $k$-subsets, because every $k$-subset covers $\binom k2$ out of $\binom n2$ pairs; this is the best possible.
When $k$ is a prime power (there exists a finite field $F$ of order $k$) and $n = k^d$, there is a construction that achieves the bound. Think of $S$ as the set $F^d$ of $d$-tuples of elements of $F$; as our $k$-subsets, take all sets of the form $S_{\mathbf x, \mathbf y} := \{\mathbf x + t \mathbf y : t \in F\}$ where $\mathbf x, \mathbf y \in F^d$ with $\mathbf y \ne \mathbf 0$. These are the lines in a $d$-dimensional affine space over $F$.
From this description, it seems like there are $n(n-1)$ sets $S_{\mathbf x, \mathbf y}$, but actually, there are only $\frac{n(n-1)}{k(k-1)}$ sets, if we don't take a set multiple times. For any $t_1, t_2 \in F$ with $t_2 \ne 0$, the set $S_{\mathbf x + t_1 \mathbf y, t_2 \mathbf y}$ is exactly the same as the set $S_{\mathbf x, \mathbf y}$. This is because we can write $\mathbf x + t \mathbf y$ as $(\mathbf x + t_1 \mathbf y) + \frac{t - t_1}{t_2}(t_2 \mathbf y)$.
For any two distinct points $\mathbf a, \mathbf b \in F^d$, the set $S_{\mathbf a, \mathbf b - \mathbf a}$ will contain both of them (and is the only set that does), so this family has the property you want. 
When we are close to having $n$ and $k$ that fit this pattern, we can round $k$ down to the nearest prime power $q$, round $n$ up to the nearest power of $q$, and then use the construction above. It will have slightly-smaller subsets of a slightly-bigger set $S$ than we wanted, but we can throw away the unnecessary elements of $S$, then pad all the subsets in our family to size $k$, and still get a result that's close to optimal.
In general, such constructions are called $(n,k,1)$-designs, or $S(2,k,n)$ Steiner systems. They exist for many, but not all, choices of $n$ and $k$.
