Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Homomorphism density
Summary
In the mathematical field of extremal graph theory, homomorphism density with respect to a graph is a parameter that is associated to each graph in the following manner:
Above, is the set of graph homomorphisms, or adjacency preserving maps, from to . Density can also be interpreted as the probability that a map from the vertices of to the vertices of chosen uniformly at random is a graph homomorphism. There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.
The edge density of a graph is given by .
The number of walks with steps is given by .
where is the adjacency matrix of .
The proportion of colorings using colors that are proper is given by .
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.
We define the (labeled) subgraph density of in to be
Note that it might be slightly dubious to call this a density, as we are not quite dividing through by the total number of labeled subgraphs on vertices of , but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of in corresponds to a homomorphism of into . However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of are sent to the same vertex of . That said, the number of such degenerate homomorphisms is only , so we have . For instance, we see that for graphs with constant homomorphism density, the labeled subgraph density and homomorphism density are asymptotically equivalent. For being a complete graph , the homomorphism density and subgraph density are in fact equal (for without self-loops), as the edges of force all images under a graph homomorphism to be distinct.
The notion of homomorphism density can be generalized to the case where instead of a graph , we have a graphon ,
Note that the integrand is a product that runs over the edges in the subgraph , whereas the differential is a product running over the vertices in .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.