4
$\begingroup$

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?

$\endgroup$

3 Answers 3

7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – JBL
    Apr 20, 2010 at 13:16
1
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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