uu.seUppsala University Publications
Change search
Refine search result
1 - 23 of 23
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Addario-Berry, Louigi
    et al.
    Broutin, Nicolas
    Holmgren, Cecilia
    Stockholms universitet, Matematiska institutionen.
    Cutting down trees with a Markov chainsaw2014In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 24, no 6, p. 2297-2339Article in journal (Refereed)
    Abstract [en]

    We provide simplified proofs for the asymptotic distribution of the number of cuts required to cut down a Galton-Watson tree with critical, finite-variance offspring distribution, conditioned to have total progeny n. Our proof is based on a coupling which yields a precise, nonasymptotic distributional result for the case of uniformly random rooted labeled trees (or, equivalently, Poisson Galton-Watson trees conditioned on their size). Our approach also provides a new, random reversible transformation between Brownian excursion and Brownian bridge.

  • 2.
    Albert, Michael
    et al.
    Univ Otago, Dept Comp Sci, Dunedin, New Zealand.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Johansson, Tony
    Stockholm Univ, Dept Math, Stockholm, Sweden.
    Skerman, Fiona
    Masaryk Univ, Fac Informat, Brno, Czech Republic.
    Embedding Small Digraphs and Permutations in Binary Trees and Split Trees2020In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 82, no 3, p. 589-615Article in journal (Refereed)
    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.

  • 3.
    Angel, Omer
    et al.
    Univ British Columbia, Dept Math, Vancouver, BC V6T 1Z2, Canada.
    van Der Hofstad, Remco
    Eindhoven Univ Technol, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Limit laws for self-loops and multiple edges in the configuration model2019In: 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)
    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.

  • 4.
    Björklund, Johan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra and Geometry.
    Falgas-Ravry, Victor
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    On percolation in one-dimensional stable Poisson graphs2015In: Electronic Communications in Probability, ISSN 1083-589X, E-ISSN 1083-589X, Vol. 20Article in journal (Refereed)
    Abstract [en]

    Equip each point x of a homogeneous Poisson point process P on R with D-x edge stubs, where the D-x are i.i.d. positive integer-valued random variables with distribution given by mu. Following the stable multi-matching scheme introduced by Deijfen, Haggstrom and Holroyd [1], we pair off edge stubs in a series of rounds to form the edge set of a graph G on the vertex set P. In this note, we answer questions of Deijfen, Holroyd and Peres [2] and Deijfen, Haggstrom and Holroyd [1] on percolation (the existence of an infinite connected component) in G. We prove that percolation may occur a.s. even if mu has support over odd integers. Furthermore, we show that for any epsilon > 0, there exists a distribution mu such that mu ({1}) > 1 - epsilon, but percolation still occurs a.s..

  • 5. Björklund, Johan
    et al.
    Holmgren, Cecilia
    University of Cambridge.
    Counterexamples to a monotonicity conjecture for the threshold pebbling number2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 15, p. 2401-2405Article in journal (Refereed)
    Abstract [en]

    Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move, in which two pebbles are removed from a vertex and one is placed on a neighbouring vertex. Given a graph G, the pebbling number pi (G) is the least t such that every initial distribution of t pebbles at the vertices of G is solvable, that is for every target vertex v, there is some list of pebbling moves that ends with v having a pebble. Given a graph sequence (G(n)), the pebbling threshold tau (G(n)) is a sequence (a(n)) such that t = a(n) is the smallest number of pebbles such that a random configuration of t pebbles on the vertices of G(n) is solvable with probability at least 1/2, in the probabilistic model where each configuration of t pebbles on the vertices of G(n) is selected uniformly at random. This paper provides counterexamples to the following monotonicity conjecture stated by Hurlbert et al.: If (G(n)) and (H(n)) are graph sequences such that pi(G(n)) <= pi(H(n)), then it holds that tau(G(n)) is an element of O(tau(H(n)).

  • 6. Bollobas, Bela
    et al.
    Gunderson, Karen
    Holmgren, Cecilia
    Stockholms universitet.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Przykucki, Michal
    Bootstrap percolation on Galton-Watson trees2014In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 19, p. 1-27Article in journal (Refereed)
    Abstract [en]

    Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number r, the r-neighbour bootstrap process is an update rule for vertices of a graph in one of two states: 'infected' or 'healthy'. In consecutive rounds, each healthy vertex with at least r infected neighbours becomes itself infected. Percolation is said to occur if every vertex is eventually infected. Usually, the starting set of infected vertices is chosen at random, with all vertices initially infected independently with probability p. In that case, given a graph G and infection threshold r, a quantity of interest is the critical probability, p(c)(G, r), at which percolation becomes likely to occur. In this paper, we look at infinite trees and, answering a problem posed by Balogh, Peres and Pete, we show that for any b >= r and for any epsilon > 0 there exists a tree T with branching number br(T) = b and critical probability p(c)(T, r) < epsilon. However, this is false if we limit ourselves to the well-studied family of Galton-Watson trees. We show that for every r >= 2 there exists a constant c(r) > 0 such that if T is a Galton-Watson tree with branching number br(T) - b >= r then pc (T, r) > c(r)/b e(-b/r-1). We also show that this bound is sharp up to a factor of O (b) by giving an explicit family of Galton-Watson trees with critical probability bounded from above by C(r)e(-b/r-1) for some constant C-r > 0.

  • 7. Bollobas, Bela
    et al.
    Holmgren, Cecilia
    Cambridge University and Stockholms universitet, Matematiska institutionen.
    Smith, Paul
    Uzzell, Andrew
    The time of bootstrap percolation with dense initial sets2014In: Annals of Probability, ISSN 0091-1798, E-ISSN 2168-894X, Vol. 42, no 4, p. 1337-1373Article in journal (Refereed)
    Abstract [en]

    Let r∈N . In r -neighbour bootstrap percolation on the vertex set of a graph G , vertices are initially infected independently with some probability p . At each time step, the infected set expands by infecting all uninfected vertices that have at least r  infected neighbours. When p  is close to 1, we study the distribution of the time at which all vertices become infected. Given t=t(n)=o(logn/loglogn) , we prove a sharp threshold result for the probability that percolation occurs by time t  in d -neighbour bootstrap percolation on the d -dimensional discrete torus T d n  . Moreover, we show that for certain ranges of p=p(n) , the time at which percolation occurs is concentrated either on a single value or on two consecutive values. We also prove corresponding results for the modified d -neighbour rule

  • 8. Broutin, Nicolas
    et al.
    Holmgren, Cecilia
    Inria and Cambridge University.
    The total path length of split trees2012In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 22, no 5, p. 1745-1777Article in journal (Refereed)
    Abstract [en]

    We consider the model of random trees introduced by Devroye [SIAM J. Comput. 28 (1999) 409–432]. The model encompasses many important randomized algorithms and data structures. The pieces of data (items) are stored in a randomized fashion in the nodes of a tree. The total path length (sum of depths of the items) is a natural measure of the efficiency of the algorithm/data structure. Using renewal theory, we prove convergence in distribution of the total path length toward a distribution characterized uniquely by a fixed point equation. Our result covers, using a unified approach, many data structures such as binary search trees, m-ary search trees, quad trees, median-of-(2k+1) trees, and simplex trees.

  • 9.
    Cai, Xing Shi
    et al.
    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.
    Cutting resilient networks - complete binary trees2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 4, article id P4.43Article in journal (Refereed)
    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].

  • 10.
    Cai, Xing Shi
    et al.
    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
    McGill Univ, Montreal, PQ, Canada.
    Skerman, Fiona
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    kappa-cut on paths and some trees2019In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 24, no 53Article in journal (Refereed)
    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.

  • 11.
    Cai, Xing Shi
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    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.
    Johansson, Tony
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Skerman, Fiona
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Inversions in Split Trees and Conditional Galton-Watson Treest2019In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 28, no 3, p. 335-364Article in journal (Refereed)
    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].

  • 12.
    Devroye, Luc
    et al.
    McGill Univ, Sch Comp Sci, 3480 Univ St, Montreal, PQ H3A 0E9, Canada.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Sulzbach, Henning
    McGill Univ, Sch Comp Sci, 3480 Univ St, Montreal, PQ H3A 0E9, Canada;Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Heavy subtrees of Galton-Watson trees with an application to Apollonian networks2019In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 24, p. 1-44, article id 2Article in journal (Refereed)
    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.

  • 13.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    A weakly 1-stable distribution for the number of random records and cuttings in split trees2011In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 43, no 1, p. 151-177Article in journal (Refereed)
    Abstract [en]

    In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

  • 14.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Novel Characteristics of Split Trees by use of Renewal Theory2012In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 17, p. 5-Article in journal (Refereed)
    Abstract [en]

    We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e. g., binary search trees, m-ary search trees, quadtrees, median of (2k + 1)-trees, simplex trees, tries and digital search trees. More precisely: We use renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality n is constructed by distributing n balls (which often represent data) to a subset of nodes of an infinite tree. One of our main results is a relation between the deterministic number of balls n and the random number of nodes N. In [5] there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth lnn/mu + O(root lnn), where mu is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of nodes with depths >= lnn/mu - ln(1/2+epsilon) n or depths <= lnn/mu + ln(1/2+epsilon) n for any choice of epsilon > 0. We also find the first asymptotic of the variances of the depths of the balls in the tree.

  • 15.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Random Records and Cuttings in Binary Search Trees2010In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 19, no 3, p. 391-424Article in journal (Refereed)
    Abstract [en]

    We study the number of random records in a  binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

  • 16.
    Holmgren, Cecilia
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Split Trees, Cuttings and Explosions2010Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”.

    In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees.

    In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees.

    In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution.

    In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.

    List of papers
    1. Random Records and Cuttings in Binary Search Trees
    Open this publication in new window or tab >>Random Records and Cuttings in Binary Search Trees
    2010 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 19, no 3, p. 391-424Article in journal (Refereed) Published
    Abstract [en]

    We study the number of random records in a  binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

    National Category
    Discrete Mathematics
    Research subject
    Mathematics
    Identifiers
    urn:nbn:se:uu:diva-112233 (URN)10.1017/S096354830999068X (DOI)000277473600004 ()
    Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2017-12-12Bibliographically approved
    2. Novel Characteristics of Split Trees by use of Renewal Theory
    Open this publication in new window or tab >>Novel Characteristics of Split Trees by use of Renewal Theory
    2012 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 17, p. 5-Article in journal (Refereed) Published
    Abstract [en]

    We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e. g., binary search trees, m-ary search trees, quadtrees, median of (2k + 1)-trees, simplex trees, tries and digital search trees. More precisely: We use renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality n is constructed by distributing n balls (which often represent data) to a subset of nodes of an infinite tree. One of our main results is a relation between the deterministic number of balls n and the random number of nodes N. In [5] there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth lnn/mu + O(root lnn), where mu is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of nodes with depths >= lnn/mu - ln(1/2+epsilon) n or depths <= lnn/mu + ln(1/2+epsilon) n for any choice of epsilon > 0. We also find the first asymptotic of the variances of the depths of the balls in the tree.

    Keywords
    Random Trees, Split Trees, Renewal Theory
    National Category
    Discrete Mathematics
    Research subject
    Mathematics
    Identifiers
    urn:nbn:se:uu:diva-112234 (URN)10.1214/EJP.v17-1723 (DOI)000301061600001 ()
    Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2017-12-12Bibliographically approved
    3. A weakly 1-stable distribution for the number of random records and cuttings in split trees
    Open this publication in new window or tab >>A weakly 1-stable distribution for the number of random records and cuttings in split trees
    2011 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 43, no 1, p. 151-177Article in journal (Refereed) Published
    Abstract [en]

    In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

    Keywords
    Random tree, split tree, cut, record, stable distribution, infinitely divisible distribution
    National Category
    Mathematics
    Research subject
    Mathematics
    Identifiers
    urn:nbn:se:uu:diva-112235 (URN)10.1239/aap/1300198517 (DOI)000289223300008 ()
    Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2017-12-12Bibliographically approved
    4. Branching Markov chains: Stability and Applications
    Open this publication in new window or tab >>Branching Markov chains: Stability and Applications
    (English)Manuscript (preprint) (Other (popular science, discussion, etc.))
    Abstract [en]

    We address the stability of certain tree algorithms used to solve the problem of communication between multiple users through a unique shared channel. We propose a general model based on branching Markov chains which allows us to write an intuitive stability condition. When the algorithm is stable, we show that there exist an asymptotic throughput, which is related to the asymptotic size of the underlying tree.

    National Category
    Discrete Mathematics
    Research subject
    Mathematics
    Identifiers
    urn:nbn:se:uu:diva-112238 (URN)
    Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2010-12-16
  • 17.
    Holmgren, Cecilia
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Broutin, Nicolas
    INRIA, Paris.
    Branching Markov chains: Stability and ApplicationsManuscript (preprint) (Other (popular science, discussion, etc.))
    Abstract [en]

    We address the stability of certain tree algorithms used to solve the problem of communication between multiple users through a unique shared channel. We propose a general model based on branching Markov chains which allows us to write an intuitive stability condition. When the algorithm is stable, we show that there exist an asymptotic throughput, which is related to the asymptotic size of the underlying tree.

  • 18.
    Holmgren, Cecilia
    et al.
    Stockholms universitet.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Asymptotic distribution of two-protected nodes in ternary search trees2015In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 20, article id 9Article in journal (Refereed)
    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

  • 19.
    Holmgren, Cecilia
    et al.
    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.
    Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees2017In: Probability Surveys, ISSN 1549-5787, E-ISSN 1549-5787, Vol. 14, p. 53-154Article in journal (Refereed)
    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.

  • 20.
    Holmgren, Cecilia
    et al.
    Stockholms universitet.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Limit laws for functions of fringe trees for binary search trees and random recursive trees2015In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 20, article id 4Article in journal (Refereed)
    Abstract [en]

    We prove general limit theorems for sums of functions of subtrees of (random) binary search trees and random recursive trees. The proofs use a new version of a representation by Devroye, and Stein's method for both normal and Poisson approximation together with certain couplings. As a consequence, we give simple new proofs of the fact that the number of fringe trees of size k = k(n) in the binary search tree or in the random recursive tree (of total size n) has an asymptotical Poisson distribution if k -> infinity, and that the distribution is asymptotically normal for k = o(root n). Furthermore, we prove similar results for the number of subtrees of size k with some required property P, e.g., the number of copies of a certain fixed subtree T. Using the Cramer-Wold device, we show also that these random numbers for different fixed subtrees converge jointly to a multivariate normal distribution. We complete the paper by giving examples of applications of the general results, e.g., we obtain a normal limit law for the number of l-protected nodes in a binary search tree or in a random recursive tree.

  • 21.
    Holmgren, Cecilia
    et al.
    Stockholms universitet, Matematiska institutionen.
    Janson, Svante
    Uppsala universitet.
    Using Stein's method to show Poisson and normal limit laws for fringe subtrees.2014In: Discrete mathematics and theoretical computer science (Online), ISSN 1462-7264, E-ISSN 1365-8050, Vol. Proc., no BA, p. 169-180Article in journal (Refereed)
    Abstract [en]

    The use of Stein’s method and certain couplings allow provision of simple proofs showing that in both of these trees, the number of fringe subtrees of size k < n, where k ! 1, can be approximated by a Poisson distribution. Combining these results and another version of Stein’s method, we can also show that for k = o(pn), the number of fringe subtrees in both types of random trees has asymptotically a normal distribution as n ! 1. Furthermore, using the Cram´er–Wold device, we show that a random vector with components corresponding to the random number of copies of certain fixed fringe subtrees Ti, has asymptotically a multivariate normal distribution. We can then use these general results on fringe subtrees to obtain simple solutions to a broad range of problems relating to random trees; as an example, we can prove that the number of protected nodes in the binary search tree has asymptotically a normal distribution.

  • 22.
    Holmgren, Cecilia
    et al.
    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
    Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Malostranske Nam 25, CR-11800 Prague, Czech Republic..
    Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees2017In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 2, article id P2.51Article in journal (Refereed)
    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.

  • 23.
    Holmgren, Cecilia
    et al.
    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..
    Juskevicius, Tomas
    Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA..
    Kettle, Nathan
    Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..
    Majority Bootstrap Percolation on G(n, p)2017In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 1, article id P1.1Article in journal (Refereed)
    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.

1 - 23 of 23
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf