Expected number of triangles in G(n,m)

Consider picking a graph with m edges on n vertices uniformly at random from the set of all graphs with n vertices and m edges. What is the expected number of triangles? Before we give an exact formula, consider the following heuristic. We can approximate this graph with a random binomial graph G(n,p) (each edge appears independently from the others with probability p)  where p=\frac{m}{{n \choose 2}}\approx \frac{2m}{n^2}. Therefore the expected number of triangles T in G should be roughly E[T]=p^3{n \choose 3}\approx\frac{8m^3}{n^6}\frac{n^3}{6}\sim \frac{4m^3}{3n^3}. This heuristic can be turned into a rigorous statement by using the asymptotic equivalence of the two random graph models. However this is a good asymptotic approximation. What about an exact formula? The simplest way is counting! How many graphs (let me mention even a bit late that we are talking about labelled graphs, which means that we have names for the vertices. For convenience we call the names by the integers 1 through n)  on n vertices do we have? Clearly {{n \choose 2} \choose m}. Consider now a triangle formed by three distinct vertices i,j,k. What is the probability of seeing this particular triangle? We have to count how many graphs contain it and divide by the total number of possible graphs. Clearly we have to use 3 edges and therefore the way of placing the rest of the edges is {{n \choose 2}-3 \choose m-3}. The expectation therefore is E[T]={n \choose 3}\frac{{{n \choose 2}-3 \choose m-3}}{{{n \choose 2} \choose m}}. QED


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: