We
comment on old and new results related to the destruction of a random recursive tree (RRT), in which its edges are cut one after the other in a uniform random order. In particular, we study the number of steps needed to isolate or disconnect certain distinguished vertices when the size of the tree tends to infinity. New probabilistic explanations are given in terms of the so-called cut-tree and the tree of component sizes, which both encode different aspects of the destruction process. Finally, we establish the connection to Bernoulli bond percolation on large RRT’s and present recent results on the cluster sizes in the supercritical regime.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Springer Professional "Wirtschaft+Technik"
Online-Abonnement
Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:
Mit dem Technik-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 40.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:
Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:
L. Addario-Berry, N. Broutin, C. Holmgren, Cutting down trees with a Markov chainsaw. Ann. Appl. Probab.
24(6), 2297–2339 (2014)
2.
D. Aldous, The Continuum Random Tree III. Ann. Probab.
21, 248–289 (1993)
CrossRefMATHMathSciNet
3.
A.-L. Barabási, R. Albert, Emergence of scaling in random networks. Science
286(5439), 509–512 (1999)
CrossRefMathSciNet
4.
D. Barraez, S. Boucheron, W. de la Fernandez, Vega, On the fluctuations of the giant component. Comb. Probab. Comput.
9, 287–304 (2000)
CrossRefMATH
5.
E. Baur, Percolation on random recursive trees. Preprint (2014).
arXiv:1407.2508
6.
J. Bertoin, Fires on trees. Ann. Inst. Henri Poincaré Probab. Stat.
48, 909–921 (2012)
CrossRefMATHMathSciNet
7.
J. Bertoin, Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Struct. Algorithms
44–1, 1098–2418 (2014)
MathSciNet
8.
J. Bertoin, On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive trees. Electron. J. Probab.
19(24), 1–15 (2014)
MathSciNet
9.
J. Bertoin, The cut-tree of large recursive trees. To appear in Ann. Instit. Henri Poincaré Probab. Stat.
10.
J. Bertoin, G. Uribe Bravo, Supercritical percolation on large scale-free random trees. To appear in Ann. Appl. Probab.
11.
J. Bertoin, G. Miermont, The cut-tree of large Galton-Watson trees and the Brownian CRT. Ann. Appl. Probab.
23, 1469–1493 (2013)
CrossRefMATHMathSciNet
12.
E. Bolthausen, A.-S. Sznitman, On Ruelle’s probability cascades and an abstract cavity method. Comm. Math. Phys.
197–2, 247–276 (1998)
CrossRefMathSciNet
13.
B. Chauvin, T. Klein, J.-F. Marckert, A. Rouault, Martingales and profile of binary search trees. Electron. J. Probab.
10, 420–435 (2005)
CrossRefMathSciNet
14.
D. Dieuleveut,The vertex-cut-tree of Galton-Watson trees converging to a stable tree. To appear in Ann. Appl. Probab.
15.
M. Drmota,
Random Trees (Springer, New York, Vienna, 2009)
CrossRefMATH
16.
M. Drmota, A. Iksanov, M. Möhle, U. Rösler, A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Struct. Algorithms
34–3, 319–336 (2009)
CrossRef
C. Goldschmidt, J.B. Martin, Random recursive trees and the Bolthausen-Sznitman coalescent. Electron. J. Probab.
10, 718–745 (2005)
CrossRefMathSciNet
19.
B. Haas, G. Miermont, Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. Ann. Probab.
40–6, 2589–2666 (2012)
CrossRefMathSciNet
20.
C. Holmgren, Random records and cuttings in binary search trees. Comb. Probab. Comput.
19–3, 391–424 (2010)
CrossRefMathSciNet
21.
C. Holmgren, A weakly 1-stable distribution for the number of random records and cuttings in split trees. Adv. Appl. Probab.
43–1, 151–177 (2011)
CrossRefMathSciNet
22.
A. Iksanov, M. Möhle, A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Comm. Probab.
12, 28–35 (2007)
CrossRefMATHMathSciNet
23.
S. Janson, Random records and cuttings in complete binary trees, in
Mathematics and Computer Science III, Algorithms, Trees, Combinatorics and Probabilities (Vienna 2004), ed. by M. Drmota, P. Flajolet, D. Gardy, B. Gittenberger (Basel, Birkhäuser, 2004), pp. 241–253
24.
S. Janson, Random cutting and records in deterministic and random trees. Random Struct. Algorithms
29–2, 139–179 (2006)
CrossRefMathSciNet
25.
O. Kallenberg,
Foundations of Modern Probability, Probability and its Applications (Springer, New York, 2002)
CrossRef
26.
M. Kuba, A. Panholzer, On the degree distribution of the nodes in increasing trees. J. Combin. Theory, Series A 114–4, 597–618 (2007)
27.
M. Kuba, A. Panholzer, Isolating nodes in recursive trees. Aequ. Math.
76, 258–280 (2008)
CrossRefMATHMathSciNet
28.
M. Kuba, A. Panholzer, Multiple isolation of nodes in recursive trees. OJAC
9, 26 (2014)
29.
H. Mahmoud,
Evolution of Random Search Trees (Wiley, New York, 1992)
MATH
30.
H. Mahmoud, R.T. Smythe, A survey of recursive trees. Theor. Probab. Math. Stat.
51, 1–29 (1994)
MATHMathSciNet
31.
A. Meir, J.W. Moon, Cutting down random trees. J. Austral. Math. Soc.
11, 313–324 (1970)
CrossRefMATHMathSciNet
32.
A. Meir, J.W. Moon, Cutting down recursive trees. Math. Biosci.
21, 173–181 (1974)
CrossRefMATH
33.
A. Panholzer, Cutting down very simple trees. Quaest. Math.
29–2, 211–227 (2006)
CrossRefMathSciNet
34.
J. Pitman, Combinatorial Stochastic Processes. École d’été de Probabilités de St. Flour, Lecture Notes in Mathematics 1875 (Springer, Berlin, 2006)
35.
B. Pittel, On tree census and the giant component in sparse random graphs. Random Struct. Algorithms
1, 311–342 (1990)
CrossRefMATHMathSciNet
36.
J. Schweinsberg, Dynamics of the evolving Bolthausen-Sznitman coalescent. Electron. J. Probab.
17, 1–50 (2012)
CrossRefMathSciNet
37.
V.E. Stepanov, On the probability of connectedness of a random graph
\(\cal {G}\)\(_m\) (t). Theory Probab. Appl.
15–1, 55–67 (1970)
Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.
Es steht fest, dass Blockchain-Technologie die Welt verändern wird. Weit weniger klar ist, wie genau dies passiert. Ein englischsprachiges Whitepaper des Fintech-Unternehmens Avaloq untersucht, welche Einsatzszenarien es im Banking und in der Vermögensverwaltung geben könnte – „Blockchain: Plausibility within Banking and Wealth Management“. Einige dieser plausiblen Einsatzszenarien haben sogar das Potenzial für eine massive Disruption. Ein bereits existierendes Beispiel liefert der Initial Coin Offering-Markt: ICO statt IPO. Jetzt gratis downloaden!
