Skip to main content
added 488 characters in body
Source Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53

(Edit: Sorry, my original restatement was incorrect.)

This problem is equivalent to decomposition a complete graph $K_n$ into a setcollection of complete graphscliques $\{K_s\}$$C:=\{K_s\}$ where each $s \leq k$, such that $C$ can be resolved (i. Ife. 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$, we havethen $C$ is a Steiner system S(2,k,n), a special type of block design, and we say $K_k$ divides $K_n$. If such a Steiner system exists, then \[\frac In this case \[|\mathcal{P}|=\frac{k}{n}|C|=\frac{k}{n}\frac{n \choose 2}{k \choose 2}\] is the minimum cardinality of the partition (inand 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$) isgives 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).

This problem is equivalent to decomposition a complete graph $K_n$ into a set of complete graphs $\{K_s\}$ where $s \leq k$. If each $s=k$, we have a Steiner system S(2,k,n), a special type of block design, and we say $K_k$ divides $K_n$. If such a Steiner system exists, then \[\frac{n \choose 2}{k \choose 2}\] is the minimum cardinality of the partition (in fact, this is always a lower bound). Although, it's not always known when a Steiner system exists (or does not exist). The case $k=3$ (and each $s=k$) is the well-known Steiner triple system which exist if and only if $n \equiv 1$ or $3 \pmod 6$.

You could find an upper bound by a greedy algorithm (starting with $K_n$, pick the largest clique $K_s$ with $s \leq k$, delete those edges and continue until you run out of edges).

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

Source Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53

This problem is equivalent to decomposition a complete graph $K_n$ into a set of complete graphs $\{K_s\}$ where $s \leq k$. If each $s=k$, we have a Steiner system S(2,k,n), a special type of block design, and we say $K_k$ divides $K_n$. If such a Steiner system exists, then \[\frac{n \choose 2}{k \choose 2}\] is the minimum cardinality of the partition (in fact, this is always a lower bound). Although, it's not always known when a Steiner system exists (or does not exist). The case $k=3$ (and each $s=k$) is the well-known Steiner triple system which exist if and only if $n \equiv 1$ or $3 \pmod 6$.

You could find an upper bound by a greedy algorithm (starting with $K_n$, pick the largest clique $K_s$ with $s \leq k$, delete those edges and continue until you run out of edges).