| 1. |
- Holroyd, Alexander E., et al.
(författare)
-
Minimal matchings of point processes
- 2022
-
Ingår i: Probability Theory and Related Fields. - : Springer Science and Business Media LLC. - 0178-8051 .- 1432-2064. ; 184:1-2, s. 571-611
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that red and blue points form independent homogeneous Poisson processes of equal intensity in R-d. For a positive (respectively, negative) parameter gamma we consider red-blue matchings that locally minimize (respectively, maximize) the sum of gamma th powers of the edge lengths, subject to locally minimizing the number of unmatched points. The parameter can be viewed as a measure of fairness. The limit gamma -> -infinity is equivalent to Gale-Shapley stable matching. We also consider limits as gamma approaches 0, 1-, 1+ and infinity. We focus on dimension d = 1. We prove that almost surely no such matching has unmatched points. (This question is open for higher d). For each gamma < 1 we establish that there is almost surely a unique such matching, and that it can be expressed as a finitary factor of the points. Moreover, its typical edge length has finite rth moment if and only if r < 1 /2. In contrast, for gamma = 1 there are uncountably many matchings, while for gamma > 1 there are countably many, but it is impossible to choose one in a translation-invariant way. We obtain existence results in higher dimensions (covering many but not all cases). We address analogous questions for one-colour matchings also.
|
|
| 2. |
- Burghart, Fabian, 1996-
(författare)
-
Building and Destroying Urns, Graphs, and Trees
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis, consisting of an introduction and four papers, different models in the mathematical area of combinatorial probability are investigated.In Paper I, two operations for combining generalised Pólya urns, called disjoint union and product, are defined. This is then shown to turn the set of isomorphism classes of Pólya urns into a semiring, and we find that assigning to an urn its intensity matrix is a semiring homomorphism.In paper II, a modification and generalisation of the random cutting model is introduced. For a finite graph with given source and target vertices, we remove vertices at random and discard all resulting components without a source node. The results concern the number of cuts needed to remove all target vertices and the size of the remaining graph, and suggest that this model interpolates between the traditional cutting model and site percolation.In paper III, we define several polynomial invariants for rooted trees based on the modified cutting model in Paper II.We find recursive identities for these invariants and, using an approach via irreducibility of polynomials, prove that two specific invariants are complete, that is, they distinguish rooted trees up to isomorphism.In paper IV, joint with Paul Thévenin, we consider an operation of concatenating t random perfect matchings on 2n vertices. Our analysis of the resulting random graph as t tends to infinity shows that there is a giant component if and only if n is odd, and that the size of this giant component as well as the number of components is asymptotically normally distributed.
|
|
| 3. |
- Janson, Svante, 1955-, et al.
(författare)
-
A modified bootstrap percolation on a random graph coupled with a lattice
- 2019
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 258, s. 152-165
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper a random graph model G(ZN2.pd) is introduced, which is a combination of fixed torus grid edges in (z/NZ)(2) and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u, v is an element of (Z/NZ)(2) with graph distance d on the torus grid is p(d) = c/Nd, where c is some constant. We show that, whp, the diameter D(G(zN2.pd)) = Theta(log N). Moreover, we consider a modified non-monotonous bootstrap percolation on G(ZN2.pd). We prove the presence of phase transitions in mean-field approximation and provide Fairly sharp bounds on the error of the critical parameters.
|
|
| 4. |
- Ahlberg, Daniel, et al.
(författare)
-
Competing first passage percolation on random graphs with finite variance degrees
- 2019
-
Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 55:3, s. 545-559
-
Tidskriftsartikel (refereegranskat)abstract
- We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate lambda(1) (lambda(2)) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if lambda(1) = lambda(2), then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V is an element of (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If lambda(1) not equal lambda(2), on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.
|
|
| 5. |
- Ahlberg, Daniel, et al.
(författare)
-
Competition in growth and urns
- 2019
-
Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 54:2, s. 211-227
-
Tidskriftsartikel (refereegranskat)abstract
- We study survival among two competing types in two settings: a planar growth model related to two-neighbor bootstrap percolation, and a system of urns with graph-based interactions. In the planar growth model, uncolored sites are given a color at rate 0, 1 or infinity, depending on whether they have zero, one, or at least two neighbors of that color. In the urn scheme, each vertex of a graph G has an associated urn containing some number of either blue or red balls ( but not both). At each time step, a ball is chosen uniformly at random from all those currently present in the system, a ball of the same color is added to each neighboring urn, and balls in the same urn but of different colors annihilate on a one-for-one basis. We show that, for every connected graph G and every initial configuration, only one color survives almost surely. As a corollary, we deduce that in the two-type growth model on Z(2), one of the colors only infects a finite number of sites with probability one. We also discuss generalizations to higher dimensions and multi-type processes, and list a number of open problems and conjectures.
|
|
| 6. |
- Ahlberg, Daniel, et al.
(författare)
-
To fixate or not to fixate in two-type annihilating branching random walks
- 2021
-
Ingår i: Annals of Probability. - : Institute of Mathematical Statistics. - 0091-1798 .- 2168-894X. ; 49:5, s. 2637-2667
-
Tidskriftsartikel (refereegranskat)abstract
- We study a model of competition between two types evolving as branching random walks on Z(d). The two types are represented by red and blue balls, respectively, with the rule that balls of different colour annihilate upon contact. We consider initial configurations in which the sites of Z(d) contain one ball each which are independently coloured red with probability p and blue otherwise. We address the question of fixation, referring to the sites and eventually settling for a given colour or not. Under a mild moment condition on the branching rule, we prove that the process will fixate almost surely for p not equal 1/2 and that every site will change colour infinitely often almost surely for the balanced initial condition p = 1/2.
|
|
| 7. |
- Bollobas, Bela, et al.
(författare)
-
Bootstrap percolation on Galton-Watson trees
- 2014
-
Ingår i: Electronic Journal of Probability. - : Univ. of Washington, Washington, USA. - 1083-6489 .- 1083-6489. ; 19, s. 1-27
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 8. |
- Ekström, Erik, et al.
(författare)
-
The inverse first-passage problem and optimal stopping
- 2016
-
Ingår i: The Annals of Applied Probability. - 1050-5164 .- 2168-8737. ; 26:5, s. 3154-3177
-
Tidskriftsartikel (refereegranskat)abstract
- Given a survival distribution on the positive half-axis and a Brownian motion, a solution of the inverse first-passage problem consists of a boundary so that the first passage time over the boundary has the given distribution. We show that the solution of the inverse first-passage problem coincides with the solution of a related optimal stopping problem. Consequently, methods from optimal stopping theory may be applied in the study of the inverse first passage problem. We illustrate this with a study of the associated integral equation for the boundary.
|
|
| 9. |
- Holmgren, Cecilia, et al.
(författare)
-
Asymptotic distribution of two-protected nodes in ternary search trees
- 2015
-
Ingår i: Electronic Journal of Probability. - 1083-6489 .- 1083-6489. ; 20
-
Tidskriftsartikel (refereegranskat)abstract
- 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
|
|
| 10. |
- Holmgren, Cecilia, et al.
(författare)
-
Limit laws for functions of fringe trees for binary search trees and random recursive trees
- 2015
-
Ingår i: Electronic Journal of Probability. - 1083-6489 .- 1083-6489. ; 20
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
