In the mathematical field of extremal graph theory, homomorphism density with respect to a graph H {\displaystyle H} is a parameter t ( H , − ) {\displaystyle t(H,-)} that is associated to each graph G {\displaystyle G} in the following manner:
t ( H , G ) := | hom ( H , G ) | | V ( G ) | | V ( H ) | {\displaystyle t(H,G):={\frac {\left|\operatorname {hom} (H,G)\right|}{|V(G)|^{|V(H)|}}}} . Above, hom ( H , G ) {\displaystyle \operatorname {hom} (H,G)} is the set of graph homomorphisms, or adjacency preserving maps, from H {\displaystyle H} to G {\displaystyle G} . Density can also be interpreted as the probability that a map from the vertices of H {\displaystyle H} to the vertices of G {\displaystyle G} chosen uniformly at random is a graph homomorphism. There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.
Examples The edge density of a graph G {\displaystyle G} is given by t ( K 2 , G ) {\displaystyle t(K_{2},G)} . The number of walks with k − 1 {\displaystyle k-1} steps is given by hom ( P k , G ) {\displaystyle \operatorname {hom} (P_{k},G)} .
hom ( C k , G ) = Tr ( A k ) {\displaystyle \operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})} where A {\displaystyle A} is the adjacency matrix of G {\displaystyle G} . The proportion of colorings using k {\displaystyle k} colors that are proper is given by t ( G , K k ) {\displaystyle t(G,K_{k})} . Other important properties such as the number of stable sets or the maximum cut can be expressed or estimated in terms of homomorphism numbers or densities.
Subgraph densities We define the (labeled) subgraph density of H {\displaystyle H} in G {\displaystyle G} to be
… excerpt ends here. Continue reading the full article.
