10
$\begingroup$

Suppose we have a complete graph $G$ of size $n$. What is the minimum number of complete graph of size $k, k<n$ needed to cover all edges of the graph $G$? Are there any results related to this problem?

$\endgroup$
  • 6
    $\begingroup$ Buzzwords "clique cover", "content decomposition", "covering number". Tons of variations. Some cases are very difficult, for example the question of whether $K_n$ can be exactly covered (no edge covered twice) by copies of $K_k$ for fixed $3\le k\le n$ is equivalent to the existence of projective planes of order $k$. $\endgroup$ – Brendan McKay Nov 6 '16 at 0:00
  • 1
    $\begingroup$ Note that I got the details wrong. See Ivan's answer for the correct version. $\endgroup$ – Brendan McKay Nov 6 '16 at 9:04
11
$\begingroup$

An equivalent reformulation of this question: if you can cover $K_n$ by $m$ cliques, what is the smallest possible size of the largest clique? For example, if $K_n$ is covered by $4$ cliques, then at least one of them has size $\frac{3n}{5}$ (which is rather surprizing, because the edge count yields a lower bound $\frac{n}{2}$). Also this $\frac{3n}{5}$ is asymptotically sharp: construct an example for $n=5$ and make multiple copies of each vertex.

The finite projective planes, as Brendan points out in his comment, can be used as follows. Vertices of the graph are points in the plane, and cliques are spanned by all points on a line. Since every pair of points lie on a unique line, every edge is covered exactly once. For a projective plane of order $k$ this gives a covering of $K_{k^2+k+1}$ by $k^2 + k + 1$ cliques of size $k+1$. Vertex multiplication gives a covering of $K_n$ by $k^2 + k + 1$ cliques of size $\frac{k+1}{k^2+k+1} n$ asymptotically. There are examples of finite projective planes for all $k$ equal to a prime power.

The most relevant reference, I think, is
P. Horák and N. Sauer, Covering complete graphs by cliques, Ars Combin. 33 (1992), 279–288.
They study several small values of $m$ that are not cardinalities of finite projective planes and find an exact estimate for the size of the largest clique. These estimates are always rational multiples of $n$ because they can be found by considering all possible Venn diagrams of the vertex sets of cliques.

By the way, here is a funny reformulation of the result stated in the first paragraph: Assume each person in a country speaks some of $4$ languages, and any two persons can communicate. Then there is a language spoken by at least $\frac{3}{5}$ of the population.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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