uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Graph properties, graph limits, and entropy
McGill Univ, Sch Comp Sci, Montreal, PQ, Canada..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
Univ Toronto, Dept Math, St George St 40, Toronto, ON M5R 2E4, Canada..
2018 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 87, no 2, p. 208-229Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
WILEY , 2018. Vol. 87, no 2, p. 208-229
Keywords [en]
graph limit, growth rate, regularity lemma, AMS Subject Classification: 05C99
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-338952DOI: 10.1002/jgt.22152ISI: 000417854500006OAI: oai:DiVA.org:uu-338952DiVA, id: diva2:1175740
Funder
Knut and Alice Wallenberg FoundationAvailable from: 2018-01-18 Created: 2018-01-18 Last updated: 2018-01-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Janson, Svante

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Probability Theory
In the same journal
Journal of Graph Theory
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 48 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf