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

Direct link
BETA
Janson, Svante
Publications (10 of 191) Show all publications
Janson, S., Kozma, R., Ruszinko, M. & Sokolov, Y. (2019). A modified bootstrap percolation on a random graph coupled with a lattice. Discrete Applied Mathematics, 258, 152-165
Open this publication in new window or tab >>A modified bootstrap percolation on a random graph coupled with a lattice
2019 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 258, p. 152-165Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Graph diameter, Degree distribution, Bootstrap percolation, Phase transitions
National Category
Probability Theory and Statistics Discrete Mathematics
Identifiers
urn:nbn:se:uu:diva-382249 (URN)10.1016/j.dam.2018.11.006 (DOI)000462694000015 ()
Funder
Knut and Alice Wallenberg Foundation, 2016.0357
Available from: 2019-05-03 Created: 2019-05-03 Last updated: 2019-05-03Bibliographically approved
Ahlberg, D., Griffiths, S., Janson, S. & Morris, R. (2019). Competition in growth and urns. Random structures & algorithms (Print), 54(2), 211-227
Open this publication in new window or tab >>Competition in growth and urns
2019 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 54, no 2, p. 211-227Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
WILEY, 2019
Keywords
bootstrap percolation, branching processes, competing growth, urn models
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-378525 (URN)10.1002/rsa.20779 (DOI)000458197400001 ()
Funder
Swedish Research Council, 637-2013-7302Knut and Alice Wallenberg FoundationEU, European Research Council, 680275 MALIG
Available from: 2019-03-25 Created: 2019-03-25 Last updated: 2019-03-25Bibliographically approved
van der Hofstad, R., Janson, S. & Luczak, M. (2019). Component structure of the configuration model: Barely supercritical case. Random structures & algorithms (Print), 55(1), 3-55
Open this publication in new window or tab >>Component structure of the configuration model: Barely supercritical case
2019 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 1, p. 3-55Article in journal (Refereed) Published
Abstract [en]

We study near-critical behavior in the configuration model. Let D-n be the degree of a random vertex and nu n=E[Dn(Dn-1)]/E[Dn]; we consider the barely supercritical regime, where nu(n)-> 1 as n ->infinity, but nu n-1 n-1/3(E[Dn3])2/3. Let Dn* denote the size-biased version of D-n. We prove that there is a unique giant component of size n rho nEDn(1+o(1)), where rho(n) denotes the survival probability of a branching process with offspring distribution Dn*-1. This extends earlier results of Janson and Luczak, as well as those of Janson, Luczak, Windridge, and House, to the case where the third moment of D-n is unbounded. We further study the size of the largest component in the critical regime, where nu n-1=O(n-1/3(EDn3)2/3), extending and complementing results of Hatami and Molloy.

Place, publisher, year, edition, pages
WILEY, 2019
Keywords
percolation, phase transition, random graphs, scaling window
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-390078 (URN)10.1002/rsa.20837 (DOI)000471321600001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-08-06 Created: 2019-08-06 Last updated: 2019-08-06Bibliographically 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
Janson, S., Shcherbakov, V. & Volkov, S. (2019). Long Term Behaviour of a Reversible System of Interacting Random Walks. Journal of statistical physics, 175(1), 71-96
Open this publication in new window or tab >>Long Term Behaviour of a Reversible System of Interacting Random Walks
2019 (English)In: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 175, no 1, p. 71-96Article in journal (Refereed) Published
Abstract [en]

This paper studies the long-term behaviour of a system of interacting random walks labelled by vertices of a finite graph. We show that the system undergoes phase transitions, with different behaviour in various regions, depending on model parameters and properties of the underlying graph. We provide the complete classification of the long-term behaviour of the corresponding continuous time Markov chain, identifying whether it is null recurrent, positive recurrent, or transient. The proofs are partially based on the reversibility of the model, which allows us to use the method of electric networks. We also provide some alternative proofs (based on the Lyapunov function method and the renewal theory), which are of interest in their own right, since they do not require reversibility and can be applied to more general situations.

Place, publisher, year, edition, pages
SPRINGER, 2019
Keywords
Markov chain, Random walk, Transience, Recurrence, Lyapunov function, Martingale, Renewal measure, Return time
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-381570 (URN)10.1007/s10955-019-02244-0 (DOI)000462211500004 ()
Funder
Knut and Alice Wallenberg FoundationSwedish Research Council, VR2014-5157
Available from: 2019-04-12 Created: 2019-04-12 Last updated: 2019-04-12Bibliographically approved
Janson, S. (2019). Patterns in random permutations avoiding the pattern 321. Random structures & algorithms (Print), 55(2), 249-270
Open this publication in new window or tab >>Patterns in random permutations avoiding the pattern 321
2019 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 2, p. 249-270Article in journal (Refereed) Published
Abstract [en]

We consider a random permutation drawn from the set of 321-avoiding permutations of length n and show that the number of occurrences of another pattern sigma has a limit distribution, after scaling by n(m + l) where m is the length of sigma and l is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.

Place, publisher, year, edition, pages
WILEY, 2019
Keywords
patterns in permutations, pattern-avoiding permutations, random permutations
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-390378 (URN)10.1002/rsa.20806 (DOI)000475814600001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-08-12 Created: 2019-08-12 Last updated: 2019-08-12Bibliographically approved
Janson, S. & Linusson, S. (2019). Proportionella val inom kommunfullmäktige.
Open this publication in new window or tab >>Proportionella val inom kommunfullmäktige
2019 (Swedish)Report (Other academic)
Abstract [sv]

Vi diskuterar två olika problem som kan uppstå vid proportionella val i kommunfullmäktige och regionfullmäktige når ett parti försöker en kupp genom att utan samtycke gå i kartell med ett annat parti vid val till nämnd eller styrelse, vilket aktualiserades i åtminstone ett par fall hösten 2018. Det första problemet är vad sådana oönskade valkarteller kan få för effekter, och vilka möjligheter det finns för ett parti att skydda sig från att bli del i en oönskad valkartell. Det andra problemet är att i en sådan valkartell kan ett parti genom att splittra upp sina kandidater strategiskt  på flera olika valsedlar få fler platser i en nämnd är vad som är proportionellt. Detta andra problem bottnar i att lagen om proportionella val stipulerar att Thieles metod skall användas för fördelning inom kartellen. På detta problem finns en enkel matematisk lösning och vi argumenterar för att man skall byta till Phragméns metod som används för motsvarande val till utskott i riksdagen.

Publisher
p. 39
National Category
Mathematics Political Science
Identifiers
urn:nbn:se:uu:diva-381790 (URN)
Funder
Knut and Alice Wallenberg FoundationSwedish Research Council, 2018-05218
Available from: 2019-04-13 Created: 2019-04-13 Last updated: 2019-04-16Bibliographically approved
Janson, S. (2019). Random Recursive Trees and Preferential Attachment Trees are Random Split Trees. Combinatorics, probability & computing, 28(1), 81-99
Open this publication in new window or tab >>Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
2019 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 28, no 1, p. 81-99Article in journal (Refereed) Published
Abstract [en]

We consider linear preferential attachment trees, and show that they can be regarded as random split trees in the sense of Devroye (1999), although with infinite potential branching. In particular, this applies to the random recursive tree and the standard preferential attachment tree. An application is given to the sum over all pairs of nodes of the common number of ancestors.

National Category
Probability Theory and Statistics Computer Sciences
Identifiers
urn:nbn:se:uu:diva-379238 (URN)10.1017/S0963548318000226 (DOI)000459867700005 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-03-19 Created: 2019-03-19 Last updated: 2019-03-19Bibliographically approved
Janson, S. (2019). Random replacements in Polya urns with infinitely many colours. Electronic Communications in Probability, 24, Article ID 23.
Open this publication in new window or tab >>Random replacements in Polya urns with infinitely many colours
2019 (English)In: Electronic Communications in Probability, ISSN 1083-589X, E-ISSN 1083-589X, Vol. 24, article id 23Article in journal (Refereed) Published
Abstract [en]

We consider the general version of Polya urns recently studied by Bandyopadhyay and Thacker (2016+) and Mailler and Marckert (2017), with the space of colours being any Borel space S and the state of the urn being a finite measure on S. We consider urns with random replacements, and show that these can be regarded as urns with deterministic replacements using the colour space S x [0, 1].

Place, publisher, year, edition, pages
UNIV WASHINGTON, DEPT MATHEMATICS, 2019
Keywords
Polya urn, infinite Polya urn, random replacements
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-384000 (URN)10.1214/19-ECP226 (DOI)000466949100001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-05-28 Created: 2019-05-28 Last updated: 2019-05-28Bibliographically approved
Janson, S. (2018). Asymptotics Of Fluctuations In Crump-Mode-Jagers Processes: The Lattice Case. Advances in Applied Probability, 50(A), 141-171
Open this publication in new window or tab >>Asymptotics Of Fluctuations In Crump-Mode-Jagers Processes: The Lattice Case
2018 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 50, no A, p. 141-171Article in journal (Refereed) Published
Abstract [en]

Consider a supercritical Crump-Mode-Jagers process in which all births are at integer times (the lattice case). Let (mu) over cap (z) be the generating function of the intensity of the offspring process, and consider the complex roots of (mu) over cap (z) = 1. The root of smallest absolute value is e(-alpha) = 1/m, where alpha > 0 is the Malthusian parameter; let gamma* be the root of second smallest absolute value. Subject to some technical conditions, the second-order fluctuations of the age distribution exhibit one of three types of behaviour: (i) when gamma* > e(-alpha/2) = m(-1/2), they are asymptotically normal; (ii) when gamma* = e(-alpha/2), they are still asymptotically normal, but with a larger variance; and (iii) when gamma* < e(-alpha/2), the fluctuations are in general oscillatory and (degenerate cases excluded) do not converge in distribution. This trichotomy is similar to what has been observed in related situations, such as some other branching processes and for Polya urns. The results lead to a symbolic calculus describing the limits. The asymptotic results also apply to the total of other (random) characteristics of the population.

Keywords
Crump-Mode-Jagers process, age distribution
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-377288 (URN)10.1017/apr.2018.76 (DOI)000457454600014 ()
Available from: 2019-02-18 Created: 2019-02-18 Last updated: 2019-02-18Bibliographically approved
Organisations

Search in DiVA

Show all publications