pith. sign in

arxiv: 1312.5626 · v1 · pith:VD54WBWVnew · submitted 2013-12-19 · 🧮 math.CO

Graph properties, graph limits and entropy

classification 🧮 math.CO
keywords graphpropertyentropygraphsrandomgraphongrowthhereditary
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.