uu.seUppsala University Publications

Please wait ... |

Link to record
http://uu.diva-portal.org/smash/person.jsf?pid=authority-person:14872 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt122_recordDirectLink",{id:"formSmash:upper:j_idt122:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt122_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt122_j_idt124",{id:"formSmash:upper:j_idt122:j_idt124",widgetVar:"widget_formSmash_upper_j_idt122_j_idt124",target:"formSmash:upper:j_idt122:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Holmgren, Cecilia

Open this publication in new window or tab >>Embedding Small Digraphs and Permutations in Binary Trees and Split Trees### Albert, Michael

### Holmgren, Cecilia

### Johansson, Tony

### Skerman, Fiona

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_some",{id:"formSmash:j_idt184:0:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_otherAuthors",{id:"formSmash:j_idt184:0:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_otherAuthors",multiple:true}); 2020 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 82, no 3, p. 589-615Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

SPRINGER, 2020
##### Keywords

Random trees, Split trees, Permutations, Inversions, Cumulants
##### National Category

Probability Theory and Statistics Computer Sciences
##### Identifiers

urn:nbn:se:uu:diva-406712 (URN)10.1007/s00453-019-00667-5 (DOI)000511594700005 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt359",{id:"formSmash:j_idt184:0:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt365",{id:"formSmash:j_idt184:0:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt371",{id:"formSmash:j_idt184:0:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg FoundationSwedish Research CouncilRagnar Söderbergs stiftelse
Available from: 2020-03-12 Created: 2020-03-12 Last updated: 2020-03-12Bibliographically approved

Univ Otago, Dept Comp Sci, Dunedin, New Zealand.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

Stockholm Univ, Dept Math, Stockholm, Sweden.

Masaryk Univ, Fac Informat, Brno, Czech Republic.

We investigate the number of permutations that occur in random labellings of trees. This is a generalisation of the number of subpermutations occurring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees (Cai et al. in Combin Probab Comput 28(3):335-364, 2019). We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye (SIAM J Comput 28(2):409-432, 1998. 10.1137/s0097539795283954). Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree, with probability tending to one as the number of balls increases, the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.

Open this publication in new window or tab >>Cutting resilient networks - complete binary trees### Cai, Xing Shi

### Holmgren, Cecilia

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_some",{id:"formSmash:j_idt184:1:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_otherAuthors",{id:"formSmash:j_idt184:1:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_otherAuthors",multiple:true}); 2019 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 4, article id P4.43Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

ELECTRONIC JOURNAL OF COMBINATORICS, 2019
##### Keywords

complete binary tree, infinitely divisible distributions, stable distributions, cuttings of trees
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:uu:diva-403240 (URN)10.37236/8350 (DOI)000506405700004 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt359",{id:"formSmash:j_idt184:1:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt365",{id:"formSmash:j_idt184:1:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt371",{id:"formSmash:j_idt184:1:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg FoundationSwedish Research CouncilRagnar Söderbergs stiftelse
Available from: 2020-01-28 Created: 2020-01-28 Last updated: 2020-01-28Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

In our previous work [2, 3], we introduced the random k-cut number for rooted graphs. In this paper, we show that the distribution of the k-cut number in complete binary trees of size n, after rescaling, is asymptotically a periodic function of lg n - lg lg n. Thus there are different limit distributions for different subsequences, where these limits are similar to weakly 1-stable distributions. This generalizes the result for the case k = 1, i.e., the traditional cutting model, by Janson [12].

Open this publication in new window or tab >>Heavy subtrees of Galton-Watson trees with an application to Apollonian networks### Devroye, Luc

### Holmgren, Cecilia

### Sulzbach, Henning

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_some",{id:"formSmash:j_idt184:2:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_otherAuthors",{id:"formSmash:j_idt184:2:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_otherAuthors",multiple:true}); 2019 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 24, p. 1-44, article id 2Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

UNIV WASHINGTON, DEPT MATHEMATICS, 2019
##### Keywords

branching processes, fringe trees, spine decomposition, binary trees, continuum random tree, Brownian excursion, exponential functionals, Apollonian networks
##### National Category

Probability Theory and Statistics
##### Identifiers

urn:nbn:se:uu:diva-377981 (URN)10.1214/19-EJP263 (DOI)000458519800001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt359",{id:"formSmash:j_idt184:2:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt365",{id:"formSmash:j_idt184:2:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt371",{id:"formSmash:j_idt184:2:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt371",multiple:true});
#####

Available from: 2019-03-04 Created: 2019-03-04 Last updated: 2019-03-04Bibliographically approved

McGill Univ, Sch Comp Sci, 3480 Univ St, Montreal, PQ H3A 0E9, Canada.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

McGill Univ, Sch Comp Sci, 3480 Univ St, Montreal, PQ H3A 0E9, Canada;Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.

We study heavy subtrees of conditional Galton-Watson trees. In a standard Galton-Watson tree conditional on its size being n, we order all children by their subtree sizes, from large (heavy) to small. A node is marked if it is among the k heaviest nodes among its siblings. Unmarked nodes and their subtrees are removed, leaving only a tree of marked nodes, which we call the k-heavy tree. We study various properties of these trees, including their size and the maximal distance from any original node to the k-heavy tree. In particular, under some moment condition, the 2-heavy tree is with high probability larger than en for some constant c > 0, and the maximal distance from the k-heavy tree is O(n(1/(k + 1)) ) in probability. As a consequence, for uniformly random Apollonian networks of size n, the expected size of the longest simple path is Omega(n). We also show that the length of the heavy path (that is, k = 1) converges (after rescaling) to the corresponding object in Aldous' Brownian continuum random tree.

Open this publication in new window or tab >>Inversions in Split Trees and Conditional Galton-Watson Treest### Cai, Xing Shi

### Holmgren, Cecilia

### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.### Johansson, Tony

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_some",{id:"formSmash:j_idt184:3:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_some",multiple:true}); ### Skerman, Fiona

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_otherAuthors",{id:"formSmash:j_idt184:3:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_3_j_idt188_j_idt202",{id:"formSmash:j_idt184:3:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2019 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 28, no 3, p. 335-364Article in journal (Refereed) Published
##### Abstract [en]

##### National Category

Probability Theory and Statistics Computer Sciences
##### Identifiers

urn:nbn:se:uu:diva-382243 (URN)10.1017/S0963548318000512 (DOI)000462848800002 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt359",{id:"formSmash:j_idt184:3:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt365",{id:"formSmash:j_idt184:3:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt371",{id:"formSmash:j_idt184:3:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg FoundationSwedish Research Council
Available from: 2019-05-15 Created: 2019-05-15 Last updated: 2019-05-15Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider X-n, the normalized version of I(T-n), for a sequence of trees T-n. For fixed T-n's, we prove a sufficient condition for X-n to converge in distribution. As an application, we identify the limit of X-n for complete b-ary trees. For T(n )being split trees [16], we show that X-n converges to the unique solution of a distributional equation. Finally, when T-n's are conditional Galton-Watson trees, we show that X-n converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].

Open this publication in new window or tab >>kappa-cut on paths and some trees### Cai, Xing Shi

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Holmgren, Cecilia

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Devroye, Luc

### Skerman, Fiona

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_some",{id:"formSmash:j_idt184:4:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_otherAuthors",{id:"formSmash:j_idt184:4:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_otherAuthors",multiple:true}); 2019 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 24, no 53Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

UNIV WASHINGTON, DEPT MATHEMATICS, 2019
##### Keywords

cutting, kappa-cut, random trees
##### National Category

Probability Theory and Statistics
##### Identifiers

urn:nbn:se:uu:diva-390273 (URN)10.1214/19-EJP318 (DOI)000472651200001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt359",{id:"formSmash:j_idt184:4:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt365",{id:"formSmash:j_idt184:4:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt371",{id:"formSmash:j_idt184:4:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg FoundationSwedish Research CouncilRagnar Söderbergs stiftelse
Available from: 2019-08-08 Created: 2019-08-08 Last updated: 2019-08-08Bibliographically approved

McGill Univ, Montreal, PQ, Canada.

We define the (random) kappa-cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon [21] except now a node must be cut kappa times before it is destroyed. The first order terms of the expectation and variance of chi(n), the kappa-cut number of a path of length n, are proved. We also show that chi(n), after rescaling, converges in distribution to a limit B-kappa, which has a complicated representation. The paper then briefly discusses the kappa-cut number of some trees and general graphs. We conclude by some analytic results which may be of interest.

Open this publication in new window or tab >>Limit laws for self-loops and multiple edges in the configuration model### Angel, Omer

### van Der Hofstad, Remco

### Holmgren, Cecilia

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_some",{id:"formSmash:j_idt184:5:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_otherAuthors",{id:"formSmash:j_idt184:5:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_otherAuthors",multiple:true}); 2019 (English)In: Annales de l'I.H.P. Probabilites et statistiques, ISSN 0246-0203, E-ISSN 1778-7017, Vol. 55, no 3, p. 1509-1530Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

INST MATHEMATICAL STATISTICS, 2019
##### Keywords

Configuration model, Self-loops, Multiple edges, Chen-Stein Poisson approximation
##### National Category

Probability Theory and Statistics
##### Identifiers

urn:nbn:se:uu:diva-395552 (URN)10.1214/18-AIHP926 (DOI)000487763200011 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt359",{id:"formSmash:j_idt184:5:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt365",{id:"formSmash:j_idt184:5:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt371",{id:"formSmash:j_idt184:5:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Swedish Research CouncilKnut and Alice Wallenberg Foundation
Available from: 2019-10-23 Created: 2019-10-23 Last updated: 2019-10-23Bibliographically approved

Univ British Columbia, Dept Math, Vancouver, BC V6T 1Z2, Canada.

Eindhoven Univ Technol, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands.

We consider self-loops and multiple edges in the configuration model as the size of the graph tends to infinity. The interest in these random variables is due to the fact that the configuration model, conditioned on being simple, is a uniform random graph with prescribed degrees. Simplicity corresponds to the absence of self-loops and multiple edges. We show that the number of self-loops and multiple edges converges in distribution to two independent Poisson random variables when the second moment of the empirical degree distribution converges. We also provide estimations on the total variation distance between the numbers of self-loops and multiple edges and their limits, as well as between the sum of these values and the Poisson random variable to which this sum converges to. This revisits previous works of Bollobas, of Janson, of Wormald and others. The error estimates also imply sharp asymptotics for the number of simple graphs with prescribed degrees. The error estimates follow from an application of the Stein-Chen method for Poisson convergence, which is a novel method for this problem. The asymptotic independence of self-loops and multiple edges follows from a Poisson version of the Cramer-Wold device using thinning, which is of independent interest. When the degree distribution has infinite second moment, our general results break down. We can, however, prove a central limit theorem for the number of self-loops, and for the multiple edges between vertices of degrees much smaller than the square root of the size of the graph. Our results and proofs easily extend to directed and bipartite configuration models.

Open this publication in new window or tab >>Fringe trees, Crump-Mode-Jagers branching processes and *m*-ary search trees### Holmgren, Cecilia

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_some",{id:"formSmash:j_idt184:6:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_otherAuthors",{id:"formSmash:j_idt184:6:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_otherAuthors",multiple:true}); 2017 (English)In: Probability Surveys, ISSN 1549-5787, E-ISSN 1549-5787, Vol. 14, p. 53-154Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

Random trees, fringe Trees, extended fringe trees, m-ary search trees, random recursive trees, preferential attachment trees, fragmentation trees, protected nodes, clades, branching processes
##### National Category

Probability Theory and Statistics
##### Identifiers

urn:nbn:se:uu:diva-334109 (URN)10.1214/16-PS272 (DOI)000408369200002 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt359",{id:"formSmash:j_idt184:6:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt365",{id:"formSmash:j_idt184:6:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt371",{id:"formSmash:j_idt184:6:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Swedish Research CouncilKnut and Alice Wallenberg Foundation
Available from: 2017-11-24 Created: 2017-11-24 Last updated: 2019-11-28Bibliographically approved

This survey studies asymptotics of random fringe trees and extended fringe trees in random trees that can be constructed as family trees of a Crump-Mode-Jagers branching process, stopped at a suitable time. This includes random recursive trees, preferential attachment trees, fragmentation trees, binary search trees and (more generally) m-ary search trees, as well as some other classes of random trees.

We begin with general results, mainly due to Aldous (1991) and Jagers and Nerman (1984). The general results are applied to fringe trees and extended fringe trees for several particular types of random trees, where the theory is developed in detail. In particular, we consider fringe trees of m-ary search trees in detail; this seems to be new.

Various applications are given, including degree distribution, protected nodes and maximal clades for various types of random trees. Again, we emphasise results for m-ary search trees, and give for example new results on protected nodes in m-ary search trees.

A separate section surveys results on the height of the random trees due to Devroye (1986), Biggins (1995, 1997) and others.

This survey contains well-known basic results together with some additional general results as well as many new examples and applications for various classes of random trees.

Open this publication in new window or tab >>Majority Bootstrap Percolation on G(n, p)### Holmgren, Cecilia

### Juskevicius, Tomas

### Kettle, Nathan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_some",{id:"formSmash:j_idt184:7:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_otherAuthors",{id:"formSmash:j_idt184:7:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_otherAuthors",multiple:true}); 2017 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 1, article id P1.1Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

bootstrap percolation, Erdos-Renyi random graph, threshold
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:uu:diva-316026 (URN)000392293400001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt359",{id:"formSmash:j_idt184:7:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt365",{id:"formSmash:j_idt184:7:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt371",{id:"formSmash:j_idt184:7:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Swedish Research Council
Available from: 2017-02-24 Created: 2017-02-24 Last updated: 2017-11-29Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory. Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..

Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA..

Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..

Majority bootstrap percolation on a graph G is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have at least half of its neighbours infected become infected. We say that percolation occurs if eventually all vertices in G become infected. In this paper we provide sharp bounds for the critical size of the initially infected set in majority bootstrap percolation on the Erdos-Renyi random graph G(n,p). This answers an open question by Janson, Luczak, Turova and Vallier (2012). Our results obtained for p = clog(n)/n are close to the results obtained by Balogh, Bollobas and Morris (2009) for majority bootstrap percolation on the hypercube. We conjecture that similar results will be true for all regular-like graphs with the same density and sufficiently strong expansion properties.

Open this publication in new window or tab >>Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees### Holmgren, Cecilia

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.### Sileikis, Matas

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_some",{id:"formSmash:j_idt184:8:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_otherAuthors",{id:"formSmash:j_idt184:8:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_otherAuthors",multiple:true}); 2017 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 2, article id P2.51Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

ELECTRONIC JOURNAL OF COMBINATORICS, 2017
##### Keywords

Random trees, Fringe trees, Normal limit laws, Polya urns, m-ary search trees, Preferential attachment trees, Protected nodes
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:uu:diva-334501 (URN)000408657300009 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt359",{id:"formSmash:j_idt184:8:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt365",{id:"formSmash:j_idt184:8:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt371",{id:"formSmash:j_idt184:8:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt371",multiple:true});
#####

Available from: 2018-01-10 Created: 2018-01-10 Last updated: 2018-01-10Bibliographically approved

Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Malostranske Nam 25, CR-11800 Prague, Czech Republic..

We study fringe subtrees of random m-ary search trees and of preferential attachment trees, by putting them in the context of generalised Polya urns. In particular we show that for the random m-ary search trees with m <= 26 and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree T converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random m-ary search trees for m <= 26 has asymptotically a normal distribution.

Open this publication in new window or tab >>Asymptotic distribution of two-protected nodes in ternary search trees### Holmgren, Cecilia

### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_some",{id:"formSmash:j_idt184:9:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_otherAuthors",{id:"formSmash:j_idt184:9:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_otherAuthors",multiple:true}); 2015 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 20, article id 9Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

Random trees, Polya urns, Normal limit laws, M-ary search trees
##### National Category

Probability Theory and Statistics
##### Identifiers

urn:nbn:se:uu:diva-248462 (URN)10.1214/EJP.v20-3577 (DOI)000350287500001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt359",{id:"formSmash:j_idt184:9:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt365",{id:"formSmash:j_idt184:9:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt371",{id:"formSmash:j_idt184:9:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt371",multiple:true});
#####

##### Funder

Swedish Research Council
Available from: 2015-03-31 Created: 2015-03-30 Last updated: 2017-12-04

Stockholms universitet.

We study protected nodes in m-ary search trees, by putting them in context of generalised Polya urns. We show that the number of two-protected nodes (the nodes that are neither leaves nor parents of leaves) in a random ternary search tree is asymptotically normal. The methods apply in principle to m-ary search trees with larger m as well, although the size of the matrices used in the calculations grow rapidly with m; we conjecture that the method yields an asymptotically normal distribution for all m <= 26. The one-protected nodes, and their complement, i.e., the leaves, are easier to analyze. By using a simpler Polya urn (that is similar to the one that has earlier been used to study the total number of nodes in m-ary search trees), we prove normal limit laws for the number of one-protected nodes and the number of leaves for all m <= 2 6