<p>Here are asymptotic bounds for <span class="math-container">$k(n, m)$</span> that are tight up to a logarithmic factor.
Note the threshold around <span class="math-container">$m = \Theta(n^{3/2})$</span>:</p>
<p><strong>Theorem 1.</strong>
<span class="math-container">$~~~~\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).$</span></p>
<p>Here's the proof.  We show the upper bounds (Lemma 1) then the lower bounds (Lemma 2).</p>
<p><strong>Lemma 1.</strong> <span class="math-container">$k(n, m) \le \min(\sqrt {n}, 2\lceil m/n\rceil)$</span></p>
<p><em>Proof.</em>  First we show <span class="math-container">$k(n, m) \le \sqrt n$</span>.
Partition the vertex greedily into some <span class="math-container">$p$</span> parts of size at most <span class="math-container">$\sqrt n/2$</span>.  Then, for each of the <span class="math-container">${p\choose 2} \le n$</span> unordered pairs <span class="math-container">$\{A, B\}$</span> of distinct parts, create a vertex set <span class="math-container">$S_i$</span> consisting of <span class="math-container">$A\cup B$</span> (having size at most <span class="math-container">$\sqrt n$</span>).  There are at most <span class="math-container">$n$</span> such pairs <span class="math-container">$\{A, B\}$</span>, and every edge has both endpoints in <span class="math-container">$A\cup B$</span> for some pair.  This shows <span class="math-container">$k(n, m) \le \sqrt n$</span>.</p>
<p>To finish we show <span class="math-container">$k(n, m) \le 2\lceil m/n\rceil$</span>.
Greedily partition the edge set <span class="math-container">$E$</span> into <span class="math-container">$n$</span> sets <span class="math-container">$E_1, \ldots, E_n$</span>
such that each contains at most <span class="math-container">$\lceil m/n\rceil$</span> edges.
For each <span class="math-container">$i\in [n]$</span>, let <span class="math-container">$S_i$</span> be the set of vertices used in edge set <span class="math-container">$E_i$</span>.
Then <span class="math-container">$|S_i| \le 2 |E_i| \le 2\lceil m/n\rceil$</span>, as desired.<span class="math-container">$~~~~\Box$</span></p>
<p>Here is the lower bound.</p>
<p><strong>Lemma 2.</strong> <span class="math-container">$k(n, m) \ge \min(\sqrt n, \lceil m/(n\ln n)\rceil)/21$</span></p>
<p><em>Proof.</em>
Let <span class="math-container">$m' = n^{3/2}\ln n$</span>.
The lower bound (of <span class="math-container">$\sqrt n/21$</span>) for <span class="math-container">$m\ge m'$</span> follows from the lower bound for <span class="math-container">$m=m'$</span>.
And a lower bound of <span class="math-container">$1$</span> holds trivially for all positive <span class="math-container">$m \le n\ln n$</span>.
So assume without loss of generality that <span class="math-container">$n\ln n \le m \le n^{3/2}\ln n$</span>.</p>
<p>Let <span class="math-container">$k=k(n, m)$</span> and <span class="math-container">$p = m/n^2$</span>.
Let <span class="math-container">$G=(V, E)$</span> be a random graph where each edge is independently present with probability <span class="math-container">$p$</span>.</p>
<p><strong>Claim 1:</strong> <em>With probability <span class="math-container">$1-o(1)$</span> <span class="math-container">$G$</span> has the following two properties:</em></p>
<ol>
<li><p><span class="math-container">$m/3 = p n^2/3 \le |E| \le p n^2 = m$</span></p>
</li>
<li><p><em>For every vertex subset <span class="math-container">$S\subseteq V$</span> of size <span class="math-container">$k$</span>,
we have <span class="math-container">$|E_S| \le 7 k \ln n$</span>,
where <span class="math-container">$E_S$</span> denotes the set of edges with both endpoints in <span class="math-container">$S$</span>.</em></p>
</li>
</ol>
<p>Suppose the claim is true.  Let <span class="math-container">$G$</span> have these two properties.
By definition of <span class="math-container">$k$</span> there are <span class="math-container">$n$</span> <span class="math-container">$k$</span>-vertex induced subgraphs in <span class="math-container">$G$</span> that collectively contain all of <span class="math-container">$G$</span>'s edges.
By Property 2, each of these <span class="math-container">$n$</span> subgraphs contains at most <span class="math-container">$7 k \ln n$</span> edges from <span class="math-container">$S$</span>,
so collectively they contain at most <span class="math-container">$7 n k \ln n$</span> edges.
But they contain <span class="math-container">$E$</span>, and (by Property 1) <span class="math-container">$|E|\ge m/3$</span>.
So <span class="math-container">$7 n k \ln n \ge m/3$</span>.  Simplifying implies <span class="math-container">$k \ge m/(21 n \ln n)$</span>, as desired.</p>
<p>To complete the proof we show the claim.
The expected number of edges in <span class="math-container">$G$</span> is <span class="math-container">${n\choose 2}p \sim n^2p/2$</span>.
By a standard Chernoff bound the probability
that <span class="math-container">$n^2p/3 \le |E| \le n^2 p$</span> fails to hold is at most <span class="math-container">$2\exp(-\Omega(n^2 p))$</span>, which (by the choice of <span class="math-container">$p$</span>) is <span class="math-container">$o(1)$</span>.
So Property 1 fails with probability <span class="math-container">$o(1)$</span>.</p>
<p>The number of <span class="math-container">$k$</span>-vertex subgraphs of <span class="math-container">$G$</span> is <span class="math-container">${n\choose k} \le n^k$</span>.
For each, (using <span class="math-container">$k \le n^{1/2}$</span> and <span class="math-container">$m\le n^{3/2}\ln n$</span>)
its expected number of edges is
<span class="math-container">${k \choose 2} p \le 3.5 k \ln n$</span>,
so by a standard Chernoff bound the probability that the number is more than <span class="math-container">$2\times 3.5 k\ln n$</span> is at most
<span class="math-container">$\exp(-3.5 k\ln (n)/3) \le \exp(-1.1 k \ln n)$</span>.
So by the naive union bound the probability that Property 2 fails is at most
<span class="math-container">$n^k \exp(-1.1 k\ln n) = \exp(-0.1 k\ln n) = o(1).$</span>
So Property 2 fails with probability <span class="math-container">$o(1)$</span>.</p>
<p>By the naive union bound, the probability that either Property 1 or Property 2 fails is <span class="math-container">$o(1)$</span>.
This proves the claim, and the lemma. <span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2023-02-03T22:23:20.390Z
2023-02-06T17:13:05.017Z
2023-02-06T17:13:05.017Z
Neal Young
<p>I want to find the smallest possible function <span class="math-container">$k(n,m)$</span> such that for any graph <span class="math-container">$G$</span> with <span class="math-container">$n$</span> vertices and <span class="math-container">$m$</span> edges, there exists <span class="math-container">$n$</span> vertex sets <span class="math-container">$S_1,S_2,...,S_n\subseteq V$</span> each with size <span class="math-container">$k(n,m)$</span> and every edge <span class="math-container">$(u,v)$</span> has <span class="math-container">$u,v$</span> both contained in some <span class="math-container">$S_i$</span>. In other words, <span class="math-container">$n$</span> complete graphs suffice to cover all edges.</p>
<p>The first question is whether <span class="math-container">$k(n,m)$</span> can be <span class="math-container">$n^{1/2-\epsilon}$</span> when <span class="math-container">$m$</span> is sub-quadratic. The question is interesting because <span class="math-container">$n$</span> complete subgraph each with size <span class="math-container">$O(n^{1/2})$</span> suffice to cover any graph.</p>
<p>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.</p>

CC BY-SA 4.0
2023-02-07T07:47:36.040Z
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$?
Christian Komusiewicz
CC BY-SA 4.0
2023-02-07T15:18:33.367Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-08T07:46:57.510Z
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.
Christian Komusiewicz
<graph-theory><graph-algorithms><co.combinatorics><combinatorics><extremal-combinatorics>
Cover a graph with complete graphs
walydna
# Cover a graph with complete graphs

(Asked by: username_0 on 2023-02-03)

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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, combinatorics, extremal-combinatorics
> **Comments:**
> **username_1**: 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$?  
> **username_2**: @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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_3 on 2023-02-03. Score: 3 | Accepted answer

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$


---

