uu.seUppsala University Publications

Please wait ... |

Link to record
http://uu.diva-portal.org/smash/person.jsf?pid=authority-person:12438 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt122_recordDirectLink",{id:"formSmash:upper:j_idt122:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt122_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt122_j_idt124",{id:"formSmash:upper:j_idt122:j_idt124",widgetVar:"widget_formSmash_upper_j_idt122_j_idt124",target:"formSmash:upper:j_idt122:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Janson, Svante

Open this publication in new window or tab >>Graph properties, graph limits, and entropy### Hatami, Hamed

### Janson, Svante

### Szegedy, Balazs

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_0_j_idt183_some",{id:"formSmash:j_idt179:0:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_0_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_0_j_idt183_otherAuthors",{id:"formSmash:j_idt179:0:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_0_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_0_j_idt183_j_idt354",{id:"formSmash:j_idt179:0:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_0_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_0_j_idt183_j_idt360",{id:"formSmash:j_idt179:0:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_0_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_0_j_idt183_j_idt366",{id:"formSmash:j_idt179:0:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_0_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-01-18 Created: 2018-01-18 Last updated: 2018-01-18Bibliographically approved

McGill Univ, Sch Comp Sci, Montreal, PQ, Canada..

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

Univ Toronto, Dept Math, St George St 40, Toronto, ON M5R 2E4, Canada..

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.

Open this publication in new window or tab >>On the critical probability in percolation### Janson, Svante

### Warnke, Lutz

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_1_j_idt183_some",{id:"formSmash:j_idt179:1:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_1_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_1_j_idt183_otherAuthors",{id:"formSmash:j_idt179:1:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_1_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_1_j_idt183_j_idt354",{id:"formSmash:j_idt179:1:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_1_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_1_j_idt183_j_idt360",{id:"formSmash:j_idt179:1:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_1_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_1_j_idt183_j_idt366",{id:"formSmash:j_idt179:1:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_1_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-02-21 Created: 2018-02-21 Last updated: 2018-02-21Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA.;Univ Cambridge Peterhouse, Cambridge CB2 1RD, England..

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.

Open this publication in new window or tab >>Tail bounds for sums of geometric and exponential variables### Janson, Svante

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_2_j_idt183_some",{id:"formSmash:j_idt179:2:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_2_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_2_j_idt183_otherAuthors",{id:"formSmash:j_idt179:2:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_2_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_2_j_idt183_j_idt354",{id:"formSmash:j_idt179:2:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_2_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_2_j_idt183_j_idt360",{id:"formSmash:j_idt179:2:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_2_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_2_j_idt183_j_idt366",{id:"formSmash:j_idt179:2:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_2_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-04-04 Created: 2018-04-04 Last updated: 2018-04-04Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

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

Open this publication in new window or tab >>Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications### Hwang, Hsien-Kuei

### Janson, Svante

### Tsai, Tsung-Hsi

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_3_j_idt183_some",{id:"formSmash:j_idt179:3:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_3_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_3_j_idt183_otherAuthors",{id:"formSmash:j_idt179:3:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_3_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_3_j_idt183_j_idt354",{id:"formSmash:j_idt179:3:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_3_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_3_j_idt183_j_idt360",{id:"formSmash:j_idt179:3:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_3_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_3_j_idt183_j_idt366",{id:"formSmash:j_idt179:3:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_3_j_idt183_j_idt366",multiple:true});
#####

Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2018-01-31Bibliographically approved

Acad Sinica, Inst Stat Sci, 128,Sec 2,Acad Rd, Taipei 11529, Taiwan..

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Acad Sinica, Inst Stat Sci, 128,Sec 2,Acad Rd, Taipei 11529, Taiwan..

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.

Open this publication in new window or tab >>Fringe trees, Crump-Mode-Jagers branching processes and *m*-ary search trees### Holmgren, Cecilia

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.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_4_j_idt183_some",{id:"formSmash:j_idt179:4:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_4_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_4_j_idt183_otherAuthors",{id:"formSmash:j_idt179:4:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_4_j_idt183_otherAuthors",multiple:true}); 2017 (English)In: Probability Surveys, ISSN 1549-5787, E-ISSN 1549-5787, Vol. 14, p. 53-154Article in journal (Refereed) Published
##### Abstract [en]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_4_j_idt183_j_idt354",{id:"formSmash:j_idt179:4:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_4_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_4_j_idt183_j_idt360",{id:"formSmash:j_idt179:4:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_4_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_4_j_idt183_j_idt366",{id:"formSmash:j_idt179:4:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_4_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Swedish Research CouncilKnut and Alice Wallenberg Foundation
Available from: 2017-11-24 Created: 2017-11-24 Last updated: 2017-11-29Bibliographically approved

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.

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### Holmgren, Cecilia

### Janson, Svante

### Sileikis, Matas

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_5_j_idt183_some",{id:"formSmash:j_idt179:5:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_5_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_5_j_idt183_otherAuthors",{id:"formSmash:j_idt179:5:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_5_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_5_j_idt183_j_idt354",{id:"formSmash:j_idt179:5:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_5_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_5_j_idt183_j_idt360",{id:"formSmash:j_idt179:5:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_5_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_5_j_idt183_j_idt366",{id:"formSmash:j_idt179:5:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_5_j_idt183_j_idt366",multiple:true});
#####

Available from: 2018-01-10 Created: 2018-01-10 Last updated: 2018-01-10Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Malostranske Nam 25, CR-11800 Prague, Czech Republic..

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.

Open this publication in new window or tab >>Near-critical SIR epidemic on a random graph with given degrees### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Luczak, Malwina

### Windridge, Peter

### House, Thomas

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_6_j_idt183_some",{id:"formSmash:j_idt179:6:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_6_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_6_j_idt183_otherAuthors",{id:"formSmash:j_idt179:6:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_6_j_idt183_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_6_j_idt183_j_idt354",{id:"formSmash:j_idt179:6:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_6_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_6_j_idt183_j_idt360",{id:"formSmash:j_idt179:6:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_6_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_6_j_idt183_j_idt366",{id:"formSmash:j_idt179:6:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_6_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2017-04-20 Created: 2017-04-20 Last updated: 2017-04-20Bibliographically approved

Queen Mary Univ London, Sch Math Sci, Mile End Rd, London E1 4NS, England..

Queen Mary Univ London, Sch Math Sci, Mile End Rd, London E1 4NS, England..

Univ Manchester, Sch Math, Manchester M13 9PL, Lancs, England..

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.

Open this publication in new window or tab >>On String Graph Limits and the Structure of a Typical String Graph### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Uzzell, Andrew J.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_7_j_idt183_some",{id:"formSmash:j_idt179:7:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_7_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_7_j_idt183_otherAuthors",{id:"formSmash:j_idt179:7:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_7_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_7_j_idt183_j_idt354",{id:"formSmash:j_idt179:7:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_7_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_7_j_idt183_j_idt360",{id:"formSmash:j_idt179:7:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_7_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_7_j_idt183_j_idt366",{id:"formSmash:j_idt179:7:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_7_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2017-05-11 Created: 2017-05-11 Last updated: 2017-05-11Bibliographically approved

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.

Open this publication in new window or tab >>Packing Random Graphs and Hypergraphs### Bollobas, Bela

### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Scott, Alex

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_8_j_idt183_some",{id:"formSmash:j_idt179:8:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_8_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_8_j_idt183_otherAuthors",{id:"formSmash:j_idt179:8:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_8_j_idt183_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_8_j_idt183_j_idt354",{id:"formSmash:j_idt179:8:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_8_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_8_j_idt183_j_idt360",{id:"formSmash:j_idt179:8:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_8_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_8_j_idt183_j_idt366",{id:"formSmash:j_idt179:8:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_8_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2017-09-13 Created: 2017-09-13 Last updated: 2017-09-13Bibliographically approved

Dept Pure Math & Math Stat, Wilberforce Rd, Cambridge CB3 0WB, England.;Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA.;London Inst Math Sci, 35a South St, London W1K 2XF, England..

Univ Oxford, Radcliffe Observ Quarter, Math Inst, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England..

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.

Open this publication in new window or tab >>The Greedy Independent Set in a Random Graph with Given Degrees### Brightwell, Graham

### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Luczak, Malwina

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_9_j_idt183_some",{id:"formSmash:j_idt179:9:j_idt183:some",widgetVar:"widget_formSmash_j_idt179_9_j_idt183_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_9_j_idt183_otherAuthors",{id:"formSmash:j_idt179:9:j_idt183:otherAuthors",widgetVar:"widget_formSmash_j_idt179_9_j_idt183_otherAuthors",multiple:true}); 2017 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 4, p. 565-586Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

greedy independent set, jamming constant, configuration model
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:uu:diva-340673 (URN)10.1002/rsa.20716 (DOI)000413405500001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_9_j_idt183_j_idt354",{id:"formSmash:j_idt179:9:j_idt183:j_idt354",widgetVar:"widget_formSmash_j_idt179_9_j_idt183_j_idt354",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_9_j_idt183_j_idt360",{id:"formSmash:j_idt179:9:j_idt183:j_idt360",widgetVar:"widget_formSmash_j_idt179_9_j_idt183_j_idt360",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt179_9_j_idt183_j_idt366",{id:"formSmash:j_idt179:9:j_idt183:j_idt366",widgetVar:"widget_formSmash_j_idt179_9_j_idt183_j_idt366",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-02-05 Created: 2018-02-05 Last updated: 2018-02-05Bibliographically approved

London Sch Econ, Dept Math, London WC2A 2AE, England..

Queen Mary Univ London, Sch Math, London, England..

We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as n (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as n. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model.