Decompose a complete graph into smaller cliques

Question

The following exercise problem is from the book of D.B.West which i could solve:

If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6.

So my questions are the following,

1. If a complete graph of $n$ vertices can be decomposed into cliques of size $p$ with $p\leq n$ then what should be the relation between $n$ and $p$.

2. What is the official name of this problem in the literature ?

Any links/hints would be helpful.

Answer 1

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: http://web.archive.org/web/20210624054646/https://www.steinertriples.fr/

If you want to decompose a complete graph into cliques of size p, the generalization of STS that you want are "Balanced Incomplete Block Designs". If you want to know more about that, try to find the book from Douglas Stinson named "Combinatorial designs: construction and analysis".

Finally, if you want to build some BIBD, we've been sweating a lot over combinatorial designs code in Sage recently. It can build a (v,k,1)-BIBD whenever one exists for k<=5, and as for larger values of k, well, it depends.

Either way, if you find a combinatorial design that it cannot build come tell us about it ! :-P

Nathann

Answer 2

I think if the size of clique, i.e. $p$ is prime, then the following statement is true.

If a complete graph of $n$ vertices can be decomposed into cliques of size p with $p≤n$ then $n-1$ or $n-p$ is divided by $p(p-1)$.

The above statement also holds if $p=2^k$.