2017/05/22 by Hamed Hatami, Svante Janson, Balázs Szegedy
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory
paper · doi:10.1002/jgt.22152
openalex publication_date 2017/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26
Abstract 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.