Graph properties, graph limits, and entropy

DOI10.1002/JGT.22152MaRDI QIDQ4604027zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, Svante Janson, Balázs Szegedy

Publication date 23 February 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.5626, http://real.mtak.hu/89853/1/1312.5626v1.pdf

zbMATH Keywords

graph limitgrowth rateregularity lemma

Mathematics Subject Classification ID

Graph theory (05C99)

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 colouring 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.

Recommendations

• scientific article; zbMATH DE number 7410277
• On extremal properties of graph entropies
• scientific article; zbMATH DE number 7410337
• scientific article; zbMATH DE number 167195
• The entropy of random-free graphons and properties
• Entropy and the complexity of graphs revisited
• Hypergraphs, entropy, and inequalities
• Szeged-like entropies of graphs
• Extremality of degree-based graph entropies
• On the von Neumann entropy of graphs

Cited in

(11)

• Sparse maximum-entropy random graphs with a given power-law degree distribution
• The entropy of random-free graphons and properties
• scientific article; zbMATH DE number 7410277 (Why is no real title available?)
• scientific article; zbMATH DE number 7410337 (Why is no real title available?)
• The penultimate rate of growth for graph properties
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• Subgraph densities and scaling limits of random graphs with a prescribed modular decomposition
• On the sampling entropy of permutons
• On the typical structure of graphs in a monotone property
• Graph limits and hereditary properties

This page was built for publication: Graph properties, graph limits, and entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604027)