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
add comment

1 Answer

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
add comment

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.