Minimum cover of partitions of a set - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T23:06:38Z http://mathoverflow.net/feeds/question/21877 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21877/minimum-cover-of-partitions-of-a-set Minimum cover of partitions of a set Diego de Estrada 2010-04-19T19:16:22Z 2010-04-20T04:50:36Z <p>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:</p> <ol> <li>Each block of every partition has at most $k$ elements.</li> <li>Every pair of elements of $N$ is in the same block in exactly one partition.</li> </ol> <p>Anyone has a clue?</p> http://mathoverflow.net/questions/21877/minimum-cover-of-partitions-of-a-set/21918#21918 Answer by akopyan for Minimum cover of partitions of a set akopyan 2010-04-20T01:31:25Z 2010-04-20T01:43:40Z <p>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. </p> <p>I think that in other cases problem is hard.</p> http://mathoverflow.net/questions/21877/minimum-cover-of-partitions-of-a-set/21921#21921 Answer by Douglas S. Stones for Minimum cover of partitions of a set Douglas S. Stones 2010-04-20T02:50:42Z 2010-04-20T04:50:36Z <p>(Edit: Sorry, my original restatement was incorrect.)</p> <p>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\}$).</p> <p>If each $s=k$, then $C$ is a <a href="http://en.wikipedia.org/wiki/Steiner_system" rel="nofollow">Steiner system</a> S(2,k,n), a special type of <a href="http://en.wikipedia.org/wiki/Block_design" rel="nofollow">block design</a>, 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 <a href="http://designtheory.org/library/encyc/sts/g/" rel="nofollow">Kirkman triple system</a>.</p> <p>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).</p> http://mathoverflow.net/questions/21877/minimum-cover-of-partitions-of-a-set/21928#21928 Answer by Gerry Myerson for Minimum cover of partitions of a set Gerry Myerson 2010-04-20T03:51:48Z 2010-04-20T03:57:26Z <p>If $k=2$, the answer is $2[(n+1)/2]-1$. </p> <p>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$. </p> <p>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$. </p> <p>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. </p> <p>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. </p> <p>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. </p>