4
$\begingroup$

Let $G=(V,E)$ be an undirected graph with $|E|=m$ edges.

Given that any clique of size $\ge 2$ can be identified with its corresponding edges, and at most every subset $S\subseteq E$ creates a clique, $G$ can have at most $|P(E)|= 2^m$ cliques of size $\ge 2$.

However, based on the intuition that it's better to arrange the edges into bigger cliques, I'd assume arranging the $m$ edges into one big clique of size $c$ is optimal (whenever it's possible). If $c$ is the size of that clique, we have $m=\binom{c}2 \rightarrow c\le 4\sqrt m$, and I'd therefore assume that one can get an upper bound of the form $2^{4\sqrt m}$.

How would one show this upper bound?

Noting in above simple proof that only subsets $S$ with size $\left|S\right|=\binom{i}2$ for some $i\in \mathbb N$ can ever be edge sets of a clique doesn't seem to help.

$\endgroup$
2
  • 1
    $\begingroup$ I would try to show that a maximum number of cliques can be achieved when the $m$ edges are incident on as few vertices as possible (which is a clique when $m$ is a triangular number). I would try to do this by showing that, given an arbitrary $m$-edge graph, if there is a vertex $v$ all of whose incident edges can be moved to other pairs of vertices that are already both of nonzero degree (note there is a wrinkle for neighbours of $v$), then doing so (which reduces the total number of vertices incident on any edge, bringing us closer to a clique) never reduces the number of cliques. $\endgroup$ Commented Aug 19, 2021 at 15:46
  • $\begingroup$ You can take a look at similar proofs of Turán's theorem for inspiration. $\endgroup$ Commented Aug 20, 2021 at 3:39

1 Answer 1

2
$\begingroup$

In this paper with DOI 10.1007/s00373-007-0738-8 we have the following theorem:

Let $n$ and $m$ be non-negative integers such that $m ≤ \binom n2$. Let $d$ and $l$ be the unique integers such that $m =\binom d2+l$, where $d ≥ 1$ and $0 ≤ l ≤ d − 1$.
Then the maximum number of cliques in an $(n, m)$-graph equals $ 2^d + 2^l + n − d − 1$.

Here, an $(n,m)$-graph is a graph with $n$ nodes and $m$ edges.

This graph has $n$ 1-cliques and $1$ 0-clique.

Therefore its number of cliques of size $\ge 2$ is $$ 2^d + 2^l − d − 2 \le 2^{d+1} − d − 2\le 2^{d+1} $$ and $d$ is the biggest integer with $m\ge \binom{d}2$.

So we further have $$ d\le \frac{\sqrt{8·m+1}+1}2 $$

Assuming $m\ge 1$, we have $$ \frac{\sqrt{8·m+1}+1}2\le \frac{\sqrt{9m}+1}2 = \frac{3\sqrt m+1}2\le 2\sqrt m $$

And with that, we get that the number of cliques of size $\ge 2$ is upper bounded by $$ 2^{2\sqrt m+1}=2\cdot 4^\sqrt m $$

$\endgroup$

Your Answer

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

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