Skip to main content
MathOverflow

Return to Answer

improved formatting
Source Link
Gerry Myerson
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247

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)$, ..., $\{\{1,n\},\{2,n-1\},\dots,\{m-1,m+1\},\{m\}\}$$(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\}$1-7, 2-6, 3-5, 4, and the others are $\{2-1,3-7,4-6,5\}$2-1, $\{3-2,4-1,5-7,6\}$3-7, $\{4-3,5-2,6-1,7\}$4-6, $\{5-4,6-3,7-2,1\}$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\}$6-5, 7-4, 1-3, 2; and $\{7-6,1-5,2-4,3\}$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\}$1-7, 2-6, 3-5, 4-8; $\{2-1,3-7,4-6,5-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.

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,n\},\{2,n-1\},\dots,\{m-1,m+1\},\{m\}\}$. 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.

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.

Source Link
Gerry Myerson
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247

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,n\},\{2,n-1\},\dots,\{m-1,m+1\},\{m\}\}$. 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.