Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Homomorphism density
Résumé
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.