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

Direct link
BETA
Janson, Svante
Publications (10 of 177) Show all publications
Hatami, H., Janson, S. & Szegedy, B. (2018). Graph properties, graph limits, and entropy. Journal of Graph Theory, 87(2), 208-229
Open this publication in new window or tab >>Graph properties, graph limits, and entropy
2018 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 87, no 2, p. 208-229Article in journal (Refereed) Published
Abstract [en]

We study the relation between the growth rate of a graph property and the entropy of the graph limits that arise from graphs with that property. In particular, for hereditary classes we obtain a new description of the coloring number, which by well-known results describes the rate of growth. We study also random graphs and their entropies. We show, for example, that if a hereditary property has a unique limiting graphon with maximal entropy, then a random graph with this property, selected uniformly at random from all such graphs with a given order, converges to this maximizing graphon as the order tends to infinity.

Place, publisher, year, edition, pages
WILEY, 2018
Keywords
graph limit, growth rate, regularity lemma, AMS Subject Classification: 05C99
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-338952 (URN)10.1002/jgt.22152 (DOI)000417854500006 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-01-18 Created: 2018-01-18 Last updated: 2018-01-18Bibliographically approved
Janson, S. & Pouyanne, N. (2018). Moment convergence of balanced Polya processes. Electronic Journal of Probability, 23, Article ID 34.
Open this publication in new window or tab >>Moment convergence of balanced Polya processes
2018 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 23, article id 34Article in journal (Refereed) Published
Abstract [en]

It is known that in an irreducible small Polya urn process, the composition of the urn after suitable normalization converges in distribution to a normal distribution. We show that if the urn also is balanced, this normal convergence holds with convergence of all moments, thus giving asymptotics of (central) moments.

Keywords
Polya urns, Polya processes, moment convergence
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-355480 (URN)10.1214/17-EJP80 (DOI)000431687400002 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-06-29 Created: 2018-06-29 Last updated: 2018-06-29Bibliographically approved
Janson, S. & Warnke, L. (2018). On the critical probability in percolation. Electronic Journal of Probability, 23, Article ID 1.
Open this publication in new window or tab >>On the critical probability in percolation
2018 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 23, article id 1Article in journal (Refereed) Published
Abstract [en]

For percolation on finite transitive graphs, Nachmias and Peres suggested a characterization of the critical probability based on the logarithmic derivative of the susceptibility. As a first test-case, we study their suggestion for the Erdos-Renyi random graph G(n,p), and confirm that the logarithmic derivative has the desired properties: (i) its maximizer lies inside the critical window p = 1/n + Theta(n(-4/3)), and (ii) the inverse of its maximum value coincides with the Theta(n(-4/3))-width of the critical window. We also prove that the maximizer is not located at p = 1/n or p = 1/(n - 1), refuting a speculation of Peres.

Place, publisher, year, edition, pages
UNIV WASHINGTON, DEPT MATHEMATICS, 2018
Keywords
random graph, percolation, phase transition, critical probability, critical window
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-342453 (URN)10.1214/17-EJP52 (DOI)000422878600001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-02-21 Created: 2018-02-21 Last updated: 2018-02-21Bibliographically approved
Janson, S. (2018). Tail bounds for sums of geometric and exponential variables. Statistics and Probability Letters, 135, 1-6
Open this publication in new window or tab >>Tail bounds for sums of geometric and exponential variables
2018 (English)In: Statistics and Probability Letters, ISSN 0167-7152, E-ISSN 1879-2103, Vol. 135, p. 1-6Article in journal (Refereed) Published
Abstract [en]

We give explicit bounds for the tail probabilities for sums of independent geometric or exponential variables, possibly with different parameters.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV, 2018
Keywords
Geometric distribution, Exponential distribution, Tail bounds
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-347533 (URN)10.1016/j.spl.2017.11.017 (DOI)000424959400001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-04-04 Created: 2018-04-04 Last updated: 2018-04-04Bibliographically approved
Hwang, H.-K., Janson, S. & Tsai, T.-H. (2017). Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications. ACM Transactions on Algorithms, 13(4), Article ID 47.
Open this publication in new window or tab >>Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications
2017 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 4, article id 47Article in journal (Refereed) Published
Abstract [en]

Divide-and-conquer recurrences of the form f (n) = f(left perpendicular n/2 right perpendicular) + f(vertical bar n/2 vertical bar) + g(n) (n >= 2), with g(n) and f(1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple identity f(n) = nP(log(2) n) - Q(n) under an optimum (iff) condition on g(n). This form is not only an identity but also an asymptotic expansion because Q(n) is of a smaller order than linearity. Explicit forms for the continuous periodic function P are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary but leads to the strongest types of results for all examples to which our theory applies.

Place, publisher, year, edition, pages
ASSOC COMPUTING MACHINERY, 2017
Keywords
Analysis of algorithms, recurrence relation, asymptotic linearity, periodic oscillation, identity, master theorems, functional equation, asymptotic approximation, uniform continuity, additivity, sensitivity analysis
National Category
Computer Sciences Mathematics
Identifiers
urn:nbn:se:uu:diva-340477 (URN)10.1145/3127585 (DOI)000419242000004 ()
Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2018-01-31Bibliographically 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: 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
Janson, S., Luczak, M., Windridge, P. & House, T. (2017). Near-critical SIR epidemic on a random graph with given degrees. Journal of Mathematical Biology, 74(4), 843-886
Open this publication in new window or tab >>Near-critical SIR epidemic on a random graph with given degrees
2017 (English)In: Journal of Mathematical Biology, ISSN 0303-6812, E-ISSN 1432-1416, Vol. 74, no 4, p. 843-886Article in journal (Refereed) Published
Abstract [en]

Emergence of new diseases and elimination of existing diseases is a key public health issue. In mathematical models of epidemics, such phenomena involve the process of infections and recoveries passing through a critical threshold where the basic reproductive ratio is 1. In this paper, we study near-critical behaviour in the context of a susceptible-infective-recovered epidemic on a random (multi)graph on n vertices with a given degree sequence. We concentrate on the regime just above the threshold for the emergence of a large epidemic, where the basic reproductive ratio is , with tending to infinity slowly as the population size, n, tends to infinity. We determine the probability that a large epidemic occurs, and the size of a large epidemic. Our results require basic regularity conditions on the degree sequences, and the assumption that the third moment of the degree of a random susceptible vertex stays uniformly bounded as . As a corollary, we determine the probability and size of a large near-critical epidemic on a standard binomial random graph in the 'sparse' regime, where the average degree is constant. As a further consequence of our method, we obtain an improved result on the size of the giant component in a random graph with given degrees just above the critical window, proving a conjecture by Janson and Luczak.

Place, publisher, year, edition, pages
SPRINGER HEIDELBERG, 2017
Keywords
SIR epidemic, Random graph with given degrees, Configuration model, Critical window
National Category
Biological Sciences Mathematics
Identifiers
urn:nbn:se:uu:diva-320409 (URN)10.1007/s00285-016-1043-z (DOI)000394299200003 ()27475950 (PubMedID)
Funder
Knut and Alice Wallenberg Foundation
Available from: 2017-04-20 Created: 2017-04-20 Last updated: 2017-04-20Bibliographically approved
Janson, S. & Uzzell, A. J. (2017). On String Graph Limits and the Structure of a Typical String Graph. Journal of Graph Theory, 84(4), 386-407
Open this publication in new window or tab >>On String Graph Limits and the Structure of a Typical String Graph
2017 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 84, no 4, p. 386-407Article in journal (Refereed) Published
Abstract [en]

We study limits of convergent sequences of string graphs, that is graphs with an intersection representation consisting of curves in the plane. We use these results to study the limiting behavior of a sequence of random string graphs. We also prove similar results for several related graph classes.

Place, publisher, year, edition, pages
WILEY, 2017
Keywords
hereditary property, graph limits, string graph
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-321854 (URN)10.1002/jgt.22031 (DOI)000398906100003 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2017-05-11 Created: 2017-05-11 Last updated: 2017-05-11Bibliographically approved
Bollobas, B., Janson, S. & Scott, A. (2017). Packing Random Graphs and Hypergraphs. Random structures & algorithms (Print), 51(1), 3-13
Open this publication in new window or tab >>Packing Random Graphs and Hypergraphs
2017 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 1, p. 3-13Article in journal (Refereed) Published
Abstract [en]

We determine to within a constant factor the threshold for the property that two random k-uniform hypergraphs with edge probability p have an edge-disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger result, on packing a random graph with a fixed graph.

Place, publisher, year, edition, pages
WILEY, 2017
Keywords
packing, random hypergraphs
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-328961 (URN)10.1002/rsa.20673 (DOI)000404127100001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2017-09-13 Created: 2017-09-13 Last updated: 2017-09-13Bibliographically approved
Organisations

Search in DiVA

Show all publications