Constructions and uses of incomplete pairwise balanced designs

Abstract

We give explicit constructions for incomplete pairwise balanced designs IPBD$((v;w),K)$, or, equivalently, edge-decompositions of a difference of two cliques $K_v\setminus K_w$ into cliques whose sizes belong to the set $K$. Our constructions produce such designs whenever $v$ and $w$ satisfy the usual divisibility conditions, have ratio $v/w$ bounded away from the smallest value in $K$ minus one, say $v/w>k-1+\epsilon$, for $k=\min K$ and $\epsilon >0$, and are sufficiently large (depending on $K$ and $\epsilon$). As a consequence, some new results are obtained on many related designs, including class-uniformly resolvable designs, incomplete mutually orthogonal latin squares, and group divisible designs. We also include several other applications that illustrate the power of using IPBDs as `templates'.