Welcome to MathOverflow

Question

3

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

flag	asked Mar 11 2012 at 2:23 Cosmin Pohoata 466●1●8

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 2012 at 2:41

Igor Rivin · Accepted Answer · 2012-03-11 02:37:43Z UTC

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)

An upper bound for number of triangles in a graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.