z-logo
Premium
Graph properties, graph limits, and entropy
Author(s) -
Hatami Hamed,
Janson Svante,
Szegedy Balázs
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22152
Subject(s) - mathematics , combinatorics , random graph , discrete mathematics , limiting , graph , mechanical engineering , engineering
We study the relation between the growth rate of a graph property and the entropy of the graph limits that arise from graphs with that property. In particular, for hereditary classes we obtain a new description of the coloring number, which by well‐known results describes the rate of growth. We study also random graphs and their entropies. We show, for example, that if a hereditary property has a unique limiting graphon with maximal entropy, then a random graph with this property, selected uniformly at random from all such graphs with a given order, converges to this maximizing graphon as the order tends to infinity.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here