Hatami, H. and Janson, Svante and Szegedy, Balázs (2018) Graph properties, graph limits, and entropy. JOURNAL OF GRAPH THEORY, 87 (2). pp. 208-229. ISSN 0364-9024
|
Text
1312.5626v1.pdf Download (336kB) | Preview |
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. © 2017 Wiley Periodicals, Inc.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | ENTROPY; growth rate; Graph theory; Subject classification; Graph properties; Random graphs; Regularity lemma; Graph limit; Hereditary property; Hereditary class; Maximal entropy; AMS Subject Classification: 05C99; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 14 Jan 2019 13:56 |
| Last Modified: | 14 Jan 2019 13:56 |
| URI: | http://real.mtak.hu/id/eprint/89853 |
Actions (login required)
 |
Edit Item |
