Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
Indeed, the construction I give can be found at en.wikipedia.org/wiki/Graph_factorization –  Gerry Myerson Apr 20 '10 at 4:07

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.

share|improve this answer
2  
A similar construction when $n = q^t$ and $k = q$ for some prime power $q$ is to identify the elements of $N$ with $(\mathbb{F}_q)^t$ and decompose the space into collections of parallel lines. –  JBL Apr 20 '10 at 13:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.