# Cover a graph with complete graphs

I want to find the smallest possible function $$k(n,m)$$ such that for any graph $$G$$ with $$n$$ vertices and $$m$$ edges, there exists $$n$$ vertex sets $$S_1,S_2,...,S_n\subseteq V$$ each with size $$k(n,m)$$ and every edge $$(u,v)$$ has $$u,v$$ both contained in some $$S_i$$. In other words, $$n$$ complete graphs suffice to cover all edges.

The first question is whether $$k(n,m)$$ can be $$n^{1/2-\epsilon}$$ when $$m$$ is sub-quadratic. The question is interesting because $$n$$ complete subgraph each with size $$O(n^{1/2})$$ suffice to cover any graph.

I searched for clique edge covering but most of the results only consider the case where cliques cannot cover non-edge. I wonder if there exists any similar research in the setting when cliques can cover non-edge.

• Just a suggestion: if I understand the problem correctly, then "subgraphs" in the title is confusing since the sets $S_i$ are not necessarily cliques in $G$? Feb 7 at 7:47
• @ChristianKomusiewicz: Indeed -- but it's about covering the graph, so I don't find it so confusing that the complete graphs used for this purpose can contain edges not part of the original graph.
– a3nm
Feb 7 at 15:18
• It's just that when one reads "Cover ... with complete subgraphs" one thinks that all the cliques must be subgraphs of the input graph. Writing "Cover a graph with complete graphs" or "Cover a graph with cliques" would be more fitting in my opinion. Feb 8 at 7:46

Here are asymptotic bounds for $$k(n, m)$$ that are tight up to a logarithmic factor. Note the threshold around $$m = \Theta(n^{3/2})$$:

Theorem 1. $$~~~~\frac{1}{21}\min(\lceil\sqrt n\rceil, \lceil m/(n\log n)\rceil) ~\le~ k(n, m) ~\le ~\min(\sqrt {n}, 2\lceil m/n\rceil).$$

Here's the proof. We show the upper bounds (Lemma 1) then the lower bounds (Lemma 2).

Lemma 1. $$k(n, m) \le \min(\sqrt {n}, 2\lceil m/n\rceil)$$

Proof. First we show $$k(n, m) \le \sqrt n$$. Partition the vertex greedily into some $$p$$ parts of size at most $$\sqrt n/2$$. Then, for each of the $${p\choose 2} \le n$$ unordered pairs $$\{A, B\}$$ of distinct parts, create a vertex set $$S_i$$ consisting of $$A\cup B$$ (having size at most $$\sqrt n$$). There are at most $$n$$ such pairs $$\{A, B\}$$, and every edge has both endpoints in $$A\cup B$$ for some pair. This shows $$k(n, m) \le \sqrt n$$.

To finish we show $$k(n, m) \le 2\lceil m/n\rceil$$. Greedily partition the edge set $$E$$ into $$n$$ sets $$E_1, \ldots, E_n$$ such that each contains at most $$\lceil m/n\rceil$$ edges. For each $$i\in [n]$$, let $$S_i$$ be the set of vertices used in edge set $$E_i$$. Then $$|S_i| \le 2 |E_i| \le 2\lceil m/n\rceil$$, as desired.$$~~~~\Box$$

Here is the lower bound.

Lemma 2. $$k(n, m) \ge \min(\sqrt n, \lceil m/(n\ln n)\rceil)/21$$

Proof. Let $$m' = n^{3/2}\ln n$$. The lower bound (of $$\sqrt n/21$$) for $$m\ge m'$$ follows from the lower bound for $$m=m'$$. And a lower bound of $$1$$ holds trivially for all positive $$m \le n\ln n$$. So assume without loss of generality that $$n\ln n \le m \le n^{3/2}\ln n$$.

Let $$k=k(n, m)$$ and $$p = m/n^2$$. Let $$G=(V, E)$$ be a random graph where each edge is independently present with probability $$p$$.

Claim 1: With probability $$1-o(1)$$ $$G$$ has the following two properties:

1. $$m/3 = p n^2/3 \le |E| \le p n^2 = m$$

2. For every vertex subset $$S\subseteq V$$ of size $$k$$, we have $$|E_S| \le 7 k \ln n$$, where $$E_S$$ denotes the set of edges with both endpoints in $$S$$.

Suppose the claim is true. Let $$G$$ have these two properties. By definition of $$k$$ there are $$n$$ $$k$$-vertex induced subgraphs in $$G$$ that collectively contain all of $$G$$'s edges. By Property 2, each of these $$n$$ subgraphs contains at most $$7 k \ln n$$ edges from $$S$$, so collectively they contain at most $$7 n k \ln n$$ edges. But they contain $$E$$, and (by Property 1) $$|E|\ge m/3$$. So $$7 n k \ln n \ge m/3$$. Simplifying implies $$k \ge m/(21 n \ln n)$$, as desired.

To complete the proof we show the claim. The expected number of edges in $$G$$ is $${n\choose 2}p \sim n^2p/2$$. By a standard Chernoff bound the probability that $$n^2p/3 \le |E| \le n^2 p$$ fails to hold is at most $$2\exp(-\Omega(n^2 p))$$, which (by the choice of $$p$$) is $$o(1)$$. So Property 1 fails with probability $$o(1)$$.

The number of $$k$$-vertex subgraphs of $$G$$ is $${n\choose k} \le n^k$$. For each, (using $$k \le n^{1/2}$$ and $$m\le n^{3/2}\ln n$$) its expected number of edges is $${k \choose 2} p \le 3.5 k \ln n$$, so by a standard Chernoff bound the probability that the number is more than $$2\times 3.5 k\ln n$$ is at most $$\exp(-3.5 k\ln (n)/3) \le \exp(-1.1 k \ln n)$$. So by the naive union bound the probability that Property 2 fails is at most $$n^k \exp(-1.1 k\ln n) = \exp(-0.1 k\ln n) = o(1).$$ So Property 2 fails with probability $$o(1)$$.

By the naive union bound, the probability that either Property 1 or Property 2 fails is $$o(1)$$. This proves the claim, and the lemma. $$~~~~\Box$$