Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T10:57:34.903Z Has data issue: false hasContentIssue false
  • English
  • Français

The Entropy of Random-Free Graphons and Properties

Published online by Cambridge University Press:  16 May 2013

HAMED HATAMI  and
SERGUEI NORINE
HAMED HATAMI
Affiliation:
School of Computer Science, McGill University, Montreal, Canada (e-mail: hatami@cs.mcgill.ca)
SERGUEI NORINE
Affiliation:
Department of Mathematics & Statistics, McGill University, Montreal, Canada (e-mail: snorin@math.mcgill.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Every graphon defines a random graph on any given number n of vertices. It was known that the graphon is random-free if and only if the entropy of this random graph is subquadratic. We prove that for random-free graphons, this entropy can grow as fast as any subquadratic function. However, if the graphon belongs to the closure of a random-free hereditary graph property, then the entropy is O(n log n). We also give a simple construction of a non-step-function random-free graphon for which this entropy is linear, refuting a conjecture of Janson.

Keywords

05C99

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 4 , July 2013 , pp. 517 - 526
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Aldous, D. J. (1985) Exchangeability and related topics. In École d'Été de Probabilités de Saint-Flour XIII, 1983, Vol. 1117 of Lecture Notes in Mathematics, Springer, pp. 1–198.Google Scholar
[2]Alon, N., Fischer, E. and Newman, I. (2007) Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM J. Comput. 37 959–976.Google Scholar
[3]Bollobás, B. (1978) Extremal Graph Theory, Vol. 11 of London Mathematical Society Monographs, Academic Press.Google Scholar
[4]Borgs, C., Chayes, J. and Lovász, L. (2010) Moments of two-variable functions and the uniqueness of graph limits. Geom. Funct. Anal. 19 1597–1619.Google Scholar
[5]Hatami, H., Janson, S. and Szegedy, B. Graph properties, graph limits and entropy. In preparation.Google Scholar
[6]Janson, S. Graphons, cut norm and distance, couplings and rearrangements. arXiv:1009.2376Google Scholar
[7]Lovász, L. and Szegedy, B. (2006) Limits of dense graph sequences. J. Combin. Theory Ser. B 96 933–957.Google Scholar
[8]Lovász, L. and Szegedy, B. (2010) Regularity partitions and the topology of graphons. In An Irregular Mind, Vol. 21 of Bolyai Soc. Math. Stud., pp. 415–446.CrossRefGoogle Scholar