An observation on edge densities of the union of isomorphic copies of a fixed graph

Consider a fixed graph H with v_H,e_H vertices and edges respectively. Assume that H is balanced which means that the maximum edge density among all possible subgraphs of H is achieved from $H$. Take two copies of H, call them H_1,H_2 and create a new graph F= H_1 \cup H_2. In case the two copies are edge disjoint then the edge density of F is the same as  the the edge density of H. If however the intersection H_1 \cap H_2 \neq \emptyset then prove that the edge density of F is greater than the edge density of H.  Recall that the edge density of a graph G is defined to be the number of edges divided by the number of vertices. If you solve the first part, use induction to generalize the statement when the number of copies is greater than 2.

It is a simple observation but turns out to be useful. The reason why I mention fixed graph in the title is because it is very useful when using the method of moments to find the number of copies of a fixed graph in G(n,p).  Use the observation to prove the following statement:

Theorem: If H is a non empty strictly balanced graph and n^{v_H}p^{e_H} \rightarrow c>0 then the number of copies of H is G(n,p) is asymptotically Poisson(\lambda) where \lambda=\frac{c^{v_H}}{aut(H)}.

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s

%d bloggers like this: