Problem
Integers $1, 2, 3, ..., n$ can form $\binom{n}{2}$ pairs of numbers.
I want to partition these pairs of numbers such that:
- The number of partition is as low as possible
- None of the partitions contains two pairs that share the same number.
How to do that?
Example
For n = 5, the following partition satisfies requirement 2:
- A: (1, 2), (3, 4)
- B: (2, 3), (4, 5)
- C: (1, 3), (2, 4)
- D: (3, 5)
- E: (1, 4), (2, 5)
- F: (1, 5)
This is an edge coloring of the complete graph $K_n$. For each color, the edges of that color will form one part of the partition.
Each color can only be used on $\lfloor \frac n2\rfloor$ edges. So we need at least $\binom n2/\lfloor \frac n2\rfloor$ colors: this is $n-1$ when $n$ is even, and $n$ when $n$ is odd.
This is in fact possible, and is explained in Wikipedia's article on Baranyai's theorem (a more general statement). The construction has a nice geometric description. Put $n-1$ vertices equally spaced in a circle and $1$ vertex at the center. For each color, pick one edge out of the central vertex, and all the edges perpendicular to that edge. Here is an image of the $n=8$ case (taken from the Wikipedia article):
For odd $n$, just use the coloring of $K_{n+1}$ obtained with this approach, and ignore edges out of vertex $n+1$.
An alternative formulation of the odd-$n$ solution is to partition pairs $\{x,y\}$ into $n$ classes based on $x+y \bmod n$. (Then $\{x,y\}$ and $\{x,z\}$ cannot be in the same class for $y \ne z$.)