Given $n,k\in\mathbb{N}$ where $k\leq n$, I want to compute the minimum subset of the set of partitions of $N$={$1,\ldots,n$}, satisfying these properties:


1. Each block of every partition has at most $k$ elements.
2. Every pair of elements of $N$ is in the same block in exactly one partition.


Anyone has a clue?



Minimum cover of partitions of a set
(Edit: Sorry, my original restatement was incorrect.)


This problem is equivalent to decomposition a complete graph $K\_n$ into a collection of cliques $C:=\{K\_s\}$ where each $s \leq k$, such that $C$ can be resolved (i.e. partitioned) into a set of resolution classes $\mathcal{P}$ (the vertices of the graphs within a resolution class partition $\{1,2,\ldots,n\}$).


If each $s=k$, then $C$ is a [Steiner system](http://en.wikipedia.org/wiki/Steiner_system) S(2,k,n), a special type of [block design](http://en.wikipedia.org/wiki/Block_design), and we say $K\_k$ divides $K\_n$. In this case \[|\mathcal{P}|=\frac{k}{n}|C|=\frac{k}{n}\frac{n \choose 2}{k \choose 2}\] and in fact, this is always a lower bound on $|\mathcal{P}|$. Although, it's not always known when a Steiner system exists (or does not exist). The case $k=3$ (and each $s=k$) gives rise to the well-known Steiner triple system which exist if and only if $n \equiv 1$ or $3 \pmod 6$. For the resolution classes to exist, we must have $n \equiv 3 \pmod 6$, whence we have a [Kirkman triple system](http://designtheory.org/library/encyc/sts/g/).


You could find an upper bound by a greedy algorithm (starting with $K\_n$, pick the largest clique $K\_s$ with $s \leq k$ from the unused vertices, delete those edges and continue until you run out of edges, starting a new part when necessary).


