8
$\begingroup$

Given a graph $G(V,E)$, what is the maximum number of triangles that this graph can have in terms of $|E|$?

I know that there is a triangle listing algorithm that lists all the triangles in $O(|E|^{3/2})$, but I need to prove that the number of triangles is actually $O(|E|^{3/2})$. Can anyone help me? Any tighter bound is also appreciated, but I need it to be based on $E$.

$\endgroup$
  • $\begingroup$ When you say maximum, do you mean over all possible graphs on a fixed number of vertices? (In which case the complete graphs clearly achieves the maximum). $\endgroup$ – Casteels Jun 7 '14 at 5:31
  • $\begingroup$ @Casteels Then $|E| = ^{|V|}C_2$. The question asks for a bound in terms of $|E|$, so clearly $|E|$ has to be fixed. Did you mean fixed number of edges with any possible number of vertices? $\endgroup$ – M. Vinay Jun 7 '14 at 5:51
  • 2
    $\begingroup$ @M.Vinay Maybe, but if $|E|$ is fixed, take as few vertices as possible to force lots of triangles and the graph will be nearly complete. Also, the complete graph has ${|V| \choose 3}$ triangles, which is $O(|E|^{3/2})$, no? $\endgroup$ – Casteels Jun 7 '14 at 6:12
  • $\begingroup$ The question is : given that you graph has $|E|$ edges, how many triangles are there in the worst case, with respect to $|E|$ only. It's harder than it sounds, really. Yes a complete graph has $O(|E|^{3/2})$ triangles, but is that the worst case ? Is there a worse setup such that you get, say, $\Theta(|E|^{3/2 + 0.1})$ triangles ? The difficulty is that $|V|$ is irrelevant here. $\endgroup$ – Manuel Lafond Jun 7 '14 at 6:15
  • $\begingroup$ @Casteels Yes, so you meant fixed number of edges, not fixed number of vertices. $\endgroup$ – M. Vinay Jun 7 '14 at 6:16
2
$\begingroup$

So far, I came up with a proof myself, but others may help verify this proof:

Lemma. Given a graph $G(V,E)$, the number of its triangles is $O(|E|^{1.5})$.

Proof. For each node $v$, let us denote by $A(v)$ the set $\{u \in N(v), d(u) \geq d(v)\}$; this set contains only neighbors of $v$ whose degree is no less than degree of $v$ itself.

Without loss of generality, let's consider each triangle $\Delta_{uvw}$ such that $d(u) \leq d(v) \leq d(w)$, where $d(v)$ is the degree of node $v$ in $G$. One may then discover $\Delta_{uvw}$ by checking that $w$ is in $A(u) \cap A(v)$.

Thus, we can claim that the set of triangles is $T=\{\Delta_{uvw} | (u,v) \in E, w \in A(u) \cap A(v)\}$. Therefore, we only need to prove that for every edge $(u,v) \in E$, the $|A(u)|$ and $|A(v)|$ are both $O(\sqrt{|E|})$.

Suppose $u$ has $\omega(\sqrt{|E|})$ such neighbors in $A(u)$. Since the degree of all of them is at least equal to the degree of $u$, the total number of edges become $\omega(|E|)$ which is a contradiction.

So we can claim that $|T| \in O(|E|^{1.5})$.

$\endgroup$
  • 1
    $\begingroup$ That's a nice way ! I think that makes sense, though to be fully convinced you'd need to show formally that $T$ misses no triangle. The last statement would also require some more detail IMO. For instance, say $u$ has $|E|^{0.51}$ neighbors in $A(u)$. Then you could say that each $v \in A(u)$ has $|E|^{0.51} - 1$ edges not incident to $u$, and that we get a total of $|E|^{0.51}(|E|^{0.51} - 1)$ edges (note that we double-count edges within $A(u)$). This is smaller than $|E|$ if $|E| = 10$ for instance. So I think you need to show there is a certain $|E|$ from which it starts working. $\endgroup$ – Manuel Lafond Jun 7 '14 at 20:15
  • $\begingroup$ @manuellafond I need to prove that $T$ doesn't miss any triangle; About the reasoning, if we approach this prove that way: For $u$ we have $|E|^{0.5}$ neighbors in $A(u)$, and for every $v \in A(u)$ we have $(|E|^{0.5}-1)$ candidates to form the triangles. Thus it should be $|V|.(|E| - |E|^{0.5})$. But we know that $|E|^{3/2}$ is a tighter bound than $|V|.|E|$. $\endgroup$ – orezvani Jun 9 '14 at 7:33
1
$\begingroup$

I'm pretty sure your proof can work out, but here's an alternative.

Let $t(e)$ be the maximum number of triangles in a graph with $e$ edges.

We want $t(e) \in O(e^{1.5})$.

As you may know, if $e = {k \choose 2}$ for some $k$, the graph with the most triangles is the complete graph on $k$ vertices, which has $O(e^{1.5})$ triangles. So we can say there is a $c$ such that $t(e) \leq ce^{1.5}$ whenever $e = {k \choose 2}$ for some $k$.

The problematic values of $e$ are those in-between binomial values, i.e. ${ k - 1 \choose 2} < e < {k \choose 2}$. I want to show these values of $e$ still "fit in" $O(e^{1.5})$. Let $\delta$ be such that $e + \delta = {k \choose 2}$. We can assume $\delta \leq e$. That's because $e + e > 2{k-1 \choose 2} > {k \choose 2}$ whenever $k > 4$, so a $\delta > e$ will never be required to reach the next binomial (for large enough $e$).

One last thing to note : $t$ is non-decreasing. That is, $t(e) \leq t(e + 1)$, because the maximum number of triangles we can make cannot decrease by adding an edge.

So here's what happens :

$$t(e) \leq t(e + \delta) \leq c(e + \delta)^{1.5} \leq c(2e)^{1.5} = 2^{1.5}ce^{1.5}$$

The first inequality because $t$ is non-decreasing, the second because $e + \delta = {k \choose 2}$, and the third because $\delta \leq e$ and "non-decreasingness".

So $t(e) \leq de^{1.5}$ with the constant $d = 2^{1.5}c$, and thus $t(e) \in O(e^{1.5})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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