4
$\begingroup$

A small inquiry about something that has been troubling me for the whole afternoon without luck: is there any known result about say simple graphs $G(V,E)$ with some property $\mathcal{P}$ such that the number of triangles $t(G)$ is bounded above by $O(|V|^{\frac{3}{2}})$?

Sorry if it is not MO appropriate :).

$\endgroup$
1
  • 1
    $\begingroup$ What kind of properties are you interested in? One such property is, for example, not containing a cycle of length 5. $\endgroup$ Mar 11, 2012 at 2:41

2 Answers 2

4
$\begingroup$

The property is that the graph be sparse, since it is easy to show that the number of triangles is $O(|E|^{3/2}),$ so as long as $E = O(V),$ your result holds. For the (simple) proof and sharp extensions see

Rivin, Igor(1-TMPL) Counting cycles and finite dimensional Lp norms. (English summary) Adv. in Appl. Math. 29 (2002), no. 4, 647–662. 05C38 (90C35)

$\endgroup$
1
  • $\begingroup$ Igor, many thanks, this is precisely what I was looking for. $\endgroup$ Apr 10, 2012 at 4:22
1
$\begingroup$

A graph is $d$-degenerate if every subgraph has minimum degree at most $d$.

Claim: Every $d$-degenerate graph with $n\geq d+1$ vertices has at most $\binom{d}{2}(n-\frac{2}{3}(d+1))$ triangles.

Proof (by induction on $n$). For the base case with $n=d+1$, the number of triangles is at most $\binom{n}{3}=\binom{d}{2}(n-\frac{2}{3}(d+1))$. Let $G$ be a $d$-degenerate graph with $n\geq d+2$ vertices. There is a vertex $v$ of degree at most $d$ in $G$. The number of triangles containing $v$ is at most $\binom{d}{2}$. The number of triangles not containing $v$ (that is, in $G-v$) is at most $\binom{d}{2}(n-1-\frac{2}{3}(d+1))$ by induction (since $G-v$ is also $d$-degenerate). In total, $G$ has at most $\binom{d}{2}(n-\frac{2}{3}(d+1))$ triangles.

This upper bound is tight for every $d$-tree.

$\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.