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)}$ .

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

Leave a Reply Cancel reply

Follow webpage via email

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

Share this:

Like this:

Leave a Reply Cancel reply

Follow webpage via email