Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T14:01:26.525Z 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: [email protected])
SERGUEI NORINE
Affiliation:
Department of Mathematics & Statistics, McGill University, Montreal, Canada (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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

05C99
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 4 , July 2013 , pp. 517 - 526
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. 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