4
$\begingroup$

In an analysis of the Jacobi method for the computation of the spectrum of a Hermitian matrix, I face the following problem.

Denote ${\cal P}_2(n)$ the set of doubletons $\{a,b\}$ in $[[1,2n]]=\{1,\ldots,2n\}$. There are $n(2n-1)$ of them. I wish to partition ${\cal P}_2(n)$ in equal parts $X_1,\ldots,X_{2n-1}$ of cardinals $n$, such that the union of the elements of any $X_\alpha$ is precisely $[[1,2n]]$ ($X_\alpha$ is a partition of $[[1,2n]]$) ? This can be viewed as a special partition of the complete graph over $2n$ vertices.

For $n=2$, there is only one solution. For $n=3$, there is a unique solution, up to a permutation in $[[1,6]]$. Is there always a solution ? Is there a natural (group theoretic ?) way to build one ?

More generally, if ${\cal P}_m(mn)$ denotes the set of parts of $[[1,mn]]$ of cardinal $m$, can it be partitionned in equal parts $X_1,\ldots,X_N$ such that each $X_\alpha$ is a partition of $[[1,mn]]$.

$\endgroup$
3
  • 2
    $\begingroup$ $$\binom{mn}{n}=n \binom{mn-1}{m-1}$$ right? $\endgroup$
    – M.U.
    Sep 3, 2015 at 21:34
  • $\begingroup$ @M.U. $\binom{mn}{m}=\frac{mn}{m}\binom{mn-1}{m-1}$ (you have a typo on the lhs) $\endgroup$
    – Suvrit
    Sep 3, 2015 at 21:37
  • $\begingroup$ ahh yes ... sorry: $\binom{mn}{m}=n\binom{mn-1}{m-1}$ $\endgroup$
    – M.U.
    Sep 3, 2015 at 21:42

1 Answer 1

11
$\begingroup$

You are asking for a 1-factorization of the complete graph $K_{2n}$. See the section "Complete graphs" of https://en.wikipedia.org/wiki/Graph_factorization for a simple description of one of them and the number of them up to $n=7$.

$\endgroup$
2
  • $\begingroup$ In particular, note Baranyai's Theorem linked from that page, which I believe corresponds to the general $m$ case. $\endgroup$ Sep 4, 2015 at 0:02
  • $\begingroup$ Nice. This page points out that a 1-factorization of the complete graph is nothing but a [round-robin] (en.wikipedia.org/wiki/Round-robin_tournament). $\endgroup$ Sep 4, 2015 at 6:34

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.