Minimum cover of partitions of a set - MathOverflow

Minimum cover of partitions of a set

2010-04-19T19:16:22Z

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:

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

Anyone has a clue?

Answer by akopyan for Minimum cover of partitions of a set

2010-04-20T01:31:25Z

If $n=\frac{p^t-1}{p-1}$ and $k=p+1$ then we can consider the set $N$ as a finite projective space and our sets be lines in this space.

I think that in other cases problem is hard.

Answer by Douglas S. Stones for Minimum cover of partitions of a set

2010-04-20T02:50:42Z

(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 S(2,k,n), a special type of 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.

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).

Answer by Gerry Myerson for Minimum cover of partitions of a set

2010-04-20T03:51:48Z

If $k=2$, the answer is $2[(n+1)/2]-1$.

If $k=2$, then there are $n\choose2$ pairs, and each partition gets at most $[n/2]$ of them, so you can't do better than ${n\choose2}/[n/2]$, which is $2[(n+1)/2]-1$. So we have to show that we can achieve $2[(n+1)/2]-1$.

First let $n=2m-1$ be odd. Let the first partition be 1-with-$n$, 2-with-$(n-1)$, ..., $(m-1)$-with-$(m+1)$,$m$-by-itself. Get the other partitions by repeatedly adding 1 to each number in the previous partition, working modulo $n$.

E.g., for $n=7$, the first partition is 1-7, 2-6, 3-5, 4, and the others are 2-1, 3-7, 4-6, 5; 3-2, 4-1, 5-7, 6; 4-3, 5-2, 6-1, 7; 5-4, 6-3, 7-2, 1; 6-5, 7-4, 1-3, 2; and 7-6, 1-5, 2-4, 3.

Now if $n=2m$ is even, just take the solution for $n=2m-1$ and in each partition pair $n$ up with the singleton. E.g., when $n=8$, the solution starts 1-7, 2-6, 3-5, 4-8; 2-1, 3-7, 4-6, 5-8; etc.

As Douglas notes, this is a problem of factoring the symmetric graph. For $k=2$ we're factoring it into 1-factors, and undoubtedly what I've written above is well-known.