nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Partition Functions of Discrete Coalescents: From Cayley’s Formula to Frieze’s ζ(3) Limit Theorem

verfasst von : Louigi Addario-Berry

Erschienen in: XI Symposium on Probability and Stochastic Processes

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In these expository notes, we describe some features of the multiplicative coalescent and its connection with random graphs and minimum spanning trees. We use Pitman’s proof (Pitman, J Combin Theory Ser A 85:165–193, 1999) of Cayley’s formula, which proceeds via a calculation of the partition function of the additive coalescent, as motivation and as a launchpad. We define a random variable which may reasonably be called the empirical partition function of the multiplicative coalescent, and show that its typical value is exponentially smaller than its expected value. Our arguments lead us to an analysis of the susceptibility of the Erdős-Rényi random graph process, and thence to a novel proof of Frieze’s ζ(3)-limit theorem for the weight of a random minimum spanning tree.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Asymptotic Spectral Distributions of Distance-k Graphs of Star Product Graphs

We find this proof of the ζ(3) limit for the MST weight pleasing, as it avoids lemmas which involve estimating the number of unicyclic and complex components in G(n, p); morally, the cycle structure of components of G(n, p) should be unimportant, since cycles are never created in Kruskal’s algorithm!

It is more common to order by reverse order of addition, so that labels increase along root-to-leaf paths; this change of perspective may help with Exercise 4.

Until further notice, we omit ceilings and floors for readability.

We omit the dependence on n in the notation for E ₁; similar infractions occur later in the proof.

To maximize ∑ _j x _j ² subject to the conditions that ∑ _j x _j = 1 and that max_j x _j ≤ δ, take x _j = δ for 1 ≤ j ≤ δ ⁻¹.

Stirling’s approximation says that \(m!/(\sqrt{2\pi m}(m/e)^{m}) \rightarrow 1\) as m → ∞; in fact the (much less precise) fact that log(m! ) = mlogm − m + o(m) is enough for the current situation.

A glance back at Figs. 2, 3 and 4 gives a hint as to the relative heights of the three trees.

Neither of these convergence statements follows from the exercises, and both require some work to prove. The fact that h(T _kc ⁽ⁿ⁾)∕logn → e in probability was first shown by Devroye [8]. The distributional convergence of h(T _ac ⁽ⁿ⁾)∕n ^1∕2 is a result of Rényi and Szekeres [15].

In fact, if edge lengths in T _ac ⁽ⁿ⁾ are multiplied by n ^−1∕2 then the resulting object converges in distribution to a random compact metric space called the Brownian continuum random tree (or CRT), and h(T _ac)∕n ^1∕2 converges in distribution to the height of the CRT. For more on this important result, we refer the reader to [4, 10].

With more care, one can show that with high probability H contains tree components containing around n ^2∕3 vertices and with height around n ^1∕3, which yields that with high probability T _mc ⁽ⁿ⁾ has height of order at least n ^1∕3.

L. Addario-Berry, N. Broutin, B. Reed, Critical random graphs and the structure of a minimum spanning tree. Random Struct. Algorithms 35, 323–347 (2009). http://www.cs.mcgill.ca/~nbrout/pub/knmst_rsa.pdf

L. Addario-Berry, N. Broutin, C. Goldschmidt, G. Miermont, The scaling limit of the minimum spanning tree of the complete graph (2013). arXiv:1301.1664 [math.PR]

D.J. Aldous, A random tree model associated with random graphs. Random Struct. Algorithms 1(4), 383–402 (1990). http://stat-www.berkeley.edu/~aldous/Papers/me49.pdf

D.J. Aldous, The continuum random tree. II. An overview, in Stochastic Analysis (Durham, 1990). Volume 167 of London Mathematical Society Lecture Note Series (Cambridge University Press, Cambridge, 1991), pp. 23–70. http://www.stat.berkeley.edu/~aldous/Papers/me55.pdf

D.J. Aldous, J.M. Steele, The objective method: probabilistic combinatorial optimization and local weak convergence. Probab. Discret. Struct. 110, 1–72 (2004). http://www.stat.berkeley.edu/~aldous/Papers/me101.pdf

E. Baur, On a ternary coalescent process. ALEA Lat. Am. J. Probab. Math. Stat. 10(2), 561–589 (2013). http://arxiv.org/pdf/1301.0409.pdf

M. Biskup, L. Chayes, S.A. Smith, Large-deviations/thermodynamic approach to percolation on the complete graph. Random Struct. Algorithms 31(3), 354–370 (2007). http://arxiv.org/abs/math/0506255

L. Devroye, A note on the height of binary search trees. J. Assoc. Comput. Mach. 33(3), 489–498 (1986). http://luc.devroye.org/devroye_1986_univ_a_note_on_the_height_of_binary_search_trees.pdf

A.M. Frieze, On the value of a random minimum spanning tree problem. Discret. Appl. Math. 10, 47–56 (1985). http://www.math.cmu.edu/~af1p/Texfiles/MST.pdf

10.

J.-F. Le Gall, Random trees and applications. Probab. Surv. 2, 245–311 (electronic) (2005). http://www.i-journals.org/ps/viewarticle.php?id=53

11.

C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics (Norwich, 1989). Volume 141 of London Mathematical Society Lecture Note Series (Cambridge University Press, Cambridge, 1989), pp. 148–188. http://www.stats.ox.ac.uk/people/academic_staff/colin_mcdiarmid/?a=4113

12.

N. O’Connell, Some large deviation results for sparse random graphs. Probab. Theory Relat. Fields 110(3), 277–285 (1998). http://homepages.warwick.ac.uk/~masgas/pubs/noc98b.pdf

13.

J. Pitman, Coalescent random forests. J. Combin. Theory Ser. A 85, 165–193 (1999). http://www.stat.berkeley.edu/~pitman/457.pdf

14.

A. Rényi, Some remarks on the theory of trees. Magyar Tud. Akad. Mat. Kutató Int. Közl. 4, 73–85 (1959)

15.

A. Rényi, G. Szekeres, On the height of trees. J. Austral. Math. Soc. 7, 497–507 (1967). http://dx.doi.org/10.1017/S1446788700004432

Titel: Partition Functions of Discrete Coalescents: From Cayley’s Formula to Frieze’s ζ(3) Limit Theorem
verfasst von: Louigi Addario-Berry
Verlag: Springer International Publishing
Buch: XI Symposium on Probability and Stochastic Processes
Print ISBN: 978-3-319-13983-8

Electronic ISBN: 978-3-319-13984-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-13984-5_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"