Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 :).

share|improve this question
1  
What kind of properties are you interested in? One such property is, for example, not containing a cycle of length 5. –  Gjergji Zaimi Mar 11 '12 at 2:41

2 Answers 2

up vote 4 down vote accepted

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)

share|improve this answer
    
Igor, many thanks, this is precisely what I was looking for. –  Cosmin Pohoata Apr 10 '12 at 4:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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