Covering Complete Graphs by Cliques

Let \(k,n\) be positive integers. Define the number \(f(k,n)\) by\\
\(f(k,n) = \min \left\{\max \left\{|S_i|: i=1,\ldots,k\right\}\right\},\)
where the minimum is taken over all \(k\)-tuples \(S_1,\ldots,S_k\) of cliques of the complete graph \(K_n\), which cover its edge set. Because there exists an \((n,m,1)\)-BIBD if and only if \(f(k,n) = m\), for \(k=\frac{n(n-1)}{m(m-1)}\), the problem of evaluating \(f(k,n)\) can also be considered as a generalization of the problem of existence of balanced incomplete block designs with \(\lambda=1\).

In the paper, the values of \(f(k,n)\) are determined for small \(k\) and some asymptotic properties of \(f\) are derived. Among others, it is shown that for all \(k\) \(\lim_{n\to\infty} \frac {f(k,n)}{n} \) exists.