uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Holmgren, Cecilia
Alternative names
Publications (10 of 23) Show all publications
Albert, M., Holmgren, C., Johansson, T. & Skerman, F. (2020). Embedding Small Digraphs and Permutations in Binary Trees and Split Trees. Algorithmica, 82(3), 589-615
Open this publication in new window or tab >>Embedding Small Digraphs and Permutations in Binary Trees and Split Trees
2020 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 82, no 3, p. 589-615Article in journal (Refereed) Published
Abstract [en]

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.

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 ()
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
Cai, X. S. & Holmgren, C. (2019). Cutting resilient networks - complete binary trees. The Electronic Journal of Combinatorics, 26(4), Article ID P4.43.
Open this publication in new window or tab >>Cutting resilient networks - complete binary trees
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]

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].

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 ()
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
Devroye, L., Holmgren, C. & Sulzbach, H. (2019). Heavy subtrees of Galton-Watson trees with an application to Apollonian networks. Electronic Journal of Probability, 24, 1-44, Article ID 2.
Open this publication in new window or tab >>Heavy subtrees of Galton-Watson trees with an application to Apollonian networks
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]

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.

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 ()
Available from: 2019-03-04 Created: 2019-03-04 Last updated: 2019-03-04Bibliographically approved
Cai, X. S., Holmgren, C., Janson, S., Johansson, T. & Skerman, F. (2019). Inversions in Split Trees and Conditional Galton-Watson Treest. Combinatorics, probability & computing, 28(3), 335-364
Open this publication in new window or tab >>Inversions in Split Trees and Conditional Galton-Watson Treest
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]

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].

National Category
Probability Theory and Statistics Computer Sciences
Identifiers
urn:nbn:se:uu:diva-382243 (URN)10.1017/S0963548318000512 (DOI)000462848800002 ()
Funder
Knut and Alice Wallenberg FoundationSwedish Research Council
Available from: 2019-05-15 Created: 2019-05-15 Last updated: 2019-05-15Bibliographically approved
Cai, X. S., Holmgren, C., Devroye, L. & Skerman, F. (2019). kappa-cut on paths and some trees. Electronic Journal of Probability, 24(53)
Open this publication in new window or tab >>kappa-cut on paths and some trees
2019 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 24, no 53Article in journal (Refereed) Published
Abstract [en]

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.

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 ()
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
Angel, O., van Der Hofstad, R. & Holmgren, C. (2019). Limit laws for self-loops and multiple edges in the configuration model. Annales de l'I.H.P. Probabilites et statistiques, 55(3), 1509-1530
Open this publication in new window or tab >>Limit laws for self-loops and multiple edges in the configuration model
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]

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.

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 ()
Funder
Swedish Research CouncilKnut and Alice Wallenberg Foundation
Available from: 2019-10-23 Created: 2019-10-23 Last updated: 2019-10-23Bibliographically approved
Holmgren, C. & Janson, S. (2017). Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees. Probability Surveys, 14, 53-154
Open this publication in new window or tab >>Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees
2017 (English)In: Probability Surveys, ISSN 1549-5787, E-ISSN 1549-5787, Vol. 14, p. 53-154Article in journal (Refereed) Published
Abstract [en]

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.

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 ()
Funder
Swedish Research CouncilKnut and Alice Wallenberg Foundation
Available from: 2017-11-24 Created: 2017-11-24 Last updated: 2019-11-28Bibliographically approved
Holmgren, C., Juskevicius, T. & Kettle, N. (2017). Majority Bootstrap Percolation on G(n, p). The Electronic Journal of Combinatorics, 24(1), Article ID P1.1.
Open this publication in new window or tab >>Majority Bootstrap Percolation on G(n, p)
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]

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.

Keywords
bootstrap percolation, Erdos-Renyi random graph, threshold
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-316026 (URN)000392293400001 ()
Funder
Swedish Research Council
Available from: 2017-02-24 Created: 2017-02-24 Last updated: 2017-11-29Bibliographically approved
Holmgren, C., Janson, S. & Sileikis, M. (2017). Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees. The Electronic Journal of Combinatorics, 24(2), Article ID P2.51.
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
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]

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.

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 ()
Available from: 2018-01-10 Created: 2018-01-10 Last updated: 2018-01-10Bibliographically approved
Holmgren, C. & Janson, S. (2015). Asymptotic distribution of two-protected nodes in ternary search trees. Electronic Journal of Probability, 20, Article ID 9.
Open this publication in new window or tab >>Asymptotic distribution of two-protected nodes in ternary search trees
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]

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

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 ()
Funder
Swedish Research Council
Available from: 2015-03-31 Created: 2015-03-30 Last updated: 2017-12-04
Organisations

Search in DiVA

Show all publications