Hostname: page-component-7c8c6479df-nwzlb Total loading time: 0 Render date: 2024-03-27T10:34:36.389Z Has data issue: false hasContentIssue false

The Entropy of Random-Free Graphons and Properties

Published online by Cambridge University Press:  16 May 2013

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)

Abstract

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

Type
Paper
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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. 1198.Google Scholar
[2]Alon, N., Fischer, E. and Newman, I. (2007) Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM J. Comput. 37 959976.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 15971619.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 933957.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