From: Dima Pasechnik <d.pasechnik@quicknet.nl>
Subject: Re: Covering the edges of a complete graph
Date: 01 May 2000 22:37:14 +0000
Newsgroups: sci.math.research
Summary: Sizes of block designs 

Mohammad Mahdian <mahdian@math.mit.edu> writes:

>  I want to cover the edges of the complete graph K_n using copies
> of K_m. How many copies do I need? This is a simple and neat
> question, so I guess there must be some results on it. Is there any
> lower bound / upper bound / asymptotics on this problem?
> 
This is well-studied in the setting of block designs 
(and their generalizations), I believe.
Indeed, your question can be trivially reformulated as asking
how many m-subsets ("blocks") of an n-set (of "points") 
so that there is a block on any pair of points.

For instance, if n=p^2+p+1 and m=p+1 then one need at least
n blocks (to form a projective plane of order p); 
(however such a set of blocks is known to exist only when p is a 
 prime power.)
This shows that the lower bound on the number of blocks obtained by a
simple counting argument (take exactly 1 block for any pair)
is sharp in the notrivial case of m>2.

HTH,
Dmitrii
d.pasechnik at its.tudelft.nl