4
$\begingroup$

Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly two of the copies of $K_m$? I've been able to find results on clique covering and the cycle double cover problem for complete graphs, but nothing on double covering by complete graphs in particular.

It may be of note that this is exactly the cycle double cover problem for $n=4$ (in which case $m$ must be $3$, and $K_3$ is a cycle), but this falls apart once $m\geq 4$. Links to resources would be much appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ This problem has a more set-combinatorial description which may be easier to find results on - you are seeking a collection of $k$ $m$-element subsets of $[n]$ such that each pair of elements is contained in exactly two of these elements. I'm afraid I cannot comment on what results there are known about this. $\endgroup$
    – Wojowu
    Commented Mar 3 at 1:21

1 Answer 1

6
$\begingroup$

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(v,k,t,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence Conjecture for $t=2$. Recently, Peter Keevash solved the Existence Conjecture in general. See the paper The existence of designs and the references therein.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.