3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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$? $\endgroup$ Feb 7 at 7:47
  • $\begingroup$ @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. $\endgroup$
    – a3nm
    Feb 7 at 15:18
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 8 at 7:46

1 Answer 1

3
$\begingroup$

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$

$\endgroup$

Your Answer

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

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