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

Direct link
BETA
Janson, Svante
Publications (10 of 197) Show all publications
Janson, S. (2020). Patterns in Random Permutations Avoiding Some Sets of Multiple Patterns. Algorithmica, 82(3), 616-641
Open this publication in new window or tab >>Patterns in Random Permutations Avoiding Some Sets of Multiple Patterns
2020 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 82, no 3, p. 616-641Article in journal (Refereed) Published
Abstract [en]

We consider a random permutation drawn from the set of permutations of length n that avoid some given set of patterns of length 3. We show that the number of occurrences of another pattern sigma has a limit distribution, after suitable scaling. In several cases, the number is asymptotically normal; this contrasts to the cases of permutations avoiding a single pattern of length 3 studied in earlier papers.

Place, publisher, year, edition, pages
SPRINGER, 2020
Keywords
Random permutations, Patterns in permutations, Forbidden patterns
National Category
Computer Sciences Discrete Mathematics
Identifiers
urn:nbn:se:uu:diva-406496 (URN)10.1007/s00453-019-00586-5 (DOI)000511594700006 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2020-03-10 Created: 2020-03-10 Last updated: 2020-03-10Bibliographically approved
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
Janson, S. & Öberg, A. (2019). A piecewise contractive dynamical system and Phragmèn's election method. Bulletin de la Société Mathématique de France, 147(3), 395-441
Open this publication in new window or tab >>A piecewise contractive dynamical system and Phragmèn's election method
2019 (English)In: Bulletin de la Société Mathématique de France, ISSN 0037-9484, E-ISSN 2102-622X, Vol. 147, no 3, p. 395-441Article in journal (Refereed) Published
Abstract [en]

We prove some basic results for a dynamical system given by a piece-wise linear and contractive map on the unit interval that takes two possible values at a point of discontinuity. We prove that there exists a universal limit cycle in the non-exceptional cases, and that the exceptional parameter set is very tiny in terms of gauge functions. The exceptional two-dimensional parameter is shown to have Hausdorff-dimension one. We also study the invariant sets and the limit sets; these are sometimes different and there are several cases to consider. In addition, we prove the existence of a unique invariant measure. We apply some of our results for the dynamical system, involving a study of rational and irrational rotation numbers, to a combinatorial problem involving an election method suggested by Phragmen, and we show that the proportion of elected seats for each party converges to a limit, which is a rational number except for a very small exceptional set of parameters.

Place, publisher, year, edition, pages
FRENCH MATHEMATICAL SOC, 2019
Keywords
piecewise contractive dynamical system, Phragmens election method
National Category
Mathematical Analysis
Identifiers
urn:nbn:se:uu:diva-396947 (URN)10.24033/bsmf.2787 (DOI)000492745100003 ()
Available from: 2019-11-21 Created: 2019-11-21 Last updated: 2019-11-21Bibliographically approved
Ahlberg, D., Deijfen, M. & Janson, S. (2019). Competing first passage percolation on random graphs with finite variance degrees. Random structures & algorithms (Print), 55(3), 545-559
Open this publication in new window or tab >>Competing first passage percolation on random graphs with finite variance degrees
2019 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 3, p. 545-559Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
WILEY, 2019
Keywords
coexistence, competing growth, configuration model, continuous-time branching process, first passage percolation, random graphs
National Category
Computer Sciences Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-393719 (URN)10.1002/rsa.20846 (DOI)000482128300002 ()
Available from: 2019-09-26 Created: 2019-09-26 Last updated: 2019-09-26Bibliographically 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., Sen, S. & Spencer, J. (2019). Preferential attachment when stable. Advances in Applied Probability, 51(4), 1067-1108
Open this publication in new window or tab >>Preferential attachment when stable
2019 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 51, no 4, p. 1067-1108Article in journal (Refereed) Published
Abstract [en]

We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the ath power (alpha > 1) of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of 2n - 2 new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, fine control of this probability may be leveraged to derive a lower- tail large deviation principle (LDP) for L= Sigma(n)(i=1) (S-i(2)/i(2)), where {S-n : n >= 0} is a simple symmetric random walk started at zero. We provide an alternative proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous-time analog of L. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process.

Place, publisher, year, edition, pages
APPLIED PROBABILITY TRUST, 2019
Keywords
Urn model, large deviations
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-398564 (URN)10.1017/apr.2019.42 (DOI)000496968500005 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-12-09 Created: 2019-12-09 Last updated: 2019-12-09Bibliographically approved
Organisations

Search in DiVA

Show all publications