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?
$\begingroup$
$\endgroup$
2
-
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 McKayCommented Nov 6, 2016 at 0:00
-
1$\begingroup$ Note that I got the details wrong. See Ivan's answer for the correct version. $\endgroup$– Brendan McKayCommented Nov 6, 2016 at 9:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Hi, I am quite out of my depths here, as I am clueless about projective planes, but how can I figure out the minimum number of 3-cliques required to cover a fully connected graph of size $n$? $\endgroup$– SagarMCommented Feb 18, 2021 at 10:53