uu.seUppsala University Publications

Please wait ... |

Refine search result

CiteExportLink to result list
http://uu.diva-portal.org/smash/resultList.jsf?query=&language=en&searchType=SIMPLE&noOfRows=50&sortOrder=author_sort_asc&sortOrder2=title_sort_asc&onlyFullText=false&sf=all&aq=%5B%5B%7B%22personId%22%3A%22authority-person%3A12438%22%7D%5D%5D&aqe=%5B%5D&aq2=%5B%5B%5D%5D&af=%5B%5D $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt1166_recordPermLink",{id:"formSmash:upper:j_idt1166:recordPermLink",widgetVar:"widget_formSmash_upper_j_idt1166_recordPermLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt1166_j_idt1168",{id:"formSmash:upper:j_idt1166:j_idt1168",widgetVar:"widget_formSmash_upper_j_idt1166_j_idt1168",target:"formSmash:upper:j_idt1166:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Cite

Citation styleapa ieee modern-language-association vancouver Other style $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt1184",{id:"formSmash:upper:j_idt1184",widgetVar:"widget_formSmash_upper_j_idt1184",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:upper:j_idt1184",e:"change",f:"formSmash",p:"formSmash:upper:j_idt1184",u:"formSmash:upper:otherStyle"},ext);}}});});

- apa
- ieee
- modern-language-association
- vancouver
- Other style

Languagede-DE en-GB en-US fi-FI nn-NO nn-NB sv-SE Other locale $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt1195",{id:"formSmash:upper:j_idt1195",widgetVar:"widget_formSmash_upper_j_idt1195",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:upper:j_idt1195",e:"change",f:"formSmash",p:"formSmash:upper:j_idt1195",u:"formSmash:upper:otherLanguage"},ext);}}});});

- de-DE
- en-GB
- en-US
- fi-FI
- nn-NO
- nn-NB
- sv-SE
- Other locale

Output formathtml text asciidoc rtf $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt1205",{id:"formSmash:upper:j_idt1205",widgetVar:"widget_formSmash_upper_j_idt1205"});});

- html
- text
- asciidoc
- rtf

Rows per page

- 5
- 10
- 20
- 50
- 100
- 250

Sort

- Standard (Relevance)
- Author A-Ö
- Author Ö-A
- Title A-Ö
- Title Ö-A
- Publication type A-Ö
- Publication type Ö-A
- Issued (Oldest first)
- Issued (Newest first)
- Created (Oldest first)
- Created (Newest first)
- Last updated (Oldest first)
- Last updated (Newest first)
- Disputation date (earliest first)
- Disputation date (latest first)

- Standard (Relevance)
- Author A-Ö
- Author Ö-A
- Title A-Ö
- Title Ö-A
- Publication type A-Ö
- Publication type Ö-A
- Issued (Oldest first)
- Issued (Newest first)
- Created (Oldest first)
- Created (Newest first)
- Last updated (Oldest first)
- Last updated (Newest first)
- Disputation date (earliest first)
- Disputation date (latest first)

Select

The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.

1. Addario-Berry, Louigi et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_0_j_idt1271",{id:"formSmash:items:resultList:0:j_idt1271",widgetVar:"widget_formSmash_items_resultList_0_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:0:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Devroye, LucJanson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:0:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees2013In: Annals of Probability, ISSN 0091-1798, E-ISSN 2168-894X, Vol. 41, no 2, p. 1072-1087Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_0_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:0:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_0_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the height and width of a Galton-Watson tree with offspring distribution xi satisfying E xi = 1, 0 < Var xi < infinity, conditioned on having exactly n nodes. Under this conditioning, we derive sub-Gaussian tail bounds for both the width (largest number of nodes in any level) and height (greatest level containing a node); the bounds are optimal up to constant factors in the exponent. Under the same conditioning, we also derive essentially optimal upper tail bounds for the number of nodes at level k, for 1 <= k <= n.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:0:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 2. Addario-Berry, Louigi et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_1_j_idt1271",{id:"formSmash:items:resultList:1:j_idt1271",widgetVar:"widget_formSmash_items_resultList_1_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:1:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.McDiarmid, ColinPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:1:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Spread of Random Graphs2014In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 23, no 4, p. 477-504Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_1_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:1:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_1_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n,d), for Erdos-Renyi random graphs G(n,p) in the supercritical range p > 1/n, and for a `small world' model. For supercritical G(n,p), we show that if p = c/n with c > 1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p = (1 + o(1))/n. Further, we show that for d large, with high probability the spread of G(n, d) becomes arbitrarily close to that of the complete graph K-n.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:1:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 3. Ahlberg, Daniel PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt1268",{id:"formSmash:items:resultList:2:j_idt1268",widgetVar:"widget_formSmash_items_resultList_2_j_idt1268",onLabel:"Ahlberg, Daniel ",offLabel:"Ahlberg, Daniel ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt1271",{id:"formSmash:items:resultList:2:j_idt1271",widgetVar:"widget_formSmash_items_resultList_2_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Stockholm Univ, Dept Math, S-10691 Stockholm, Sweden.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:2:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Deijfen, MariaStockholm Univ, Dept Math, S-10691 Stockholm, Sweden.Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:2:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Competing first passage percolation on random graphs with finite variance degrees2019In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 3, p. 545-559Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:2:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_2_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:2:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 4. Ahlberg, Daniel PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt1268",{id:"formSmash:items:resultList:3:j_idt1268",widgetVar:"widget_formSmash_items_resultList_3_j_idt1268",onLabel:"Ahlberg, Daniel ",offLabel:"Ahlberg, Daniel ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt1271",{id:"formSmash:items:resultList:3:j_idt1271",widgetVar:"widget_formSmash_items_resultList_3_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Stockholm Univ, Dept Math, SE-10691 Stockholm, Sweden.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:3:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Griffiths, SimonPUC Rio, Dept Matemat, BR-22451900 Gavea, RJ, Brazil.Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Morris, RobertInst Nacl Matemat Pura & Aplicada, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro, Brazil.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:3:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Competition in growth and urns2019In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 54, no 2, p. 211-227Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:3:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_3_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:3:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 5. Alm, Sven Erick PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt1268",{id:"formSmash:items:resultList:4:j_idt1268",widgetVar:"widget_formSmash_items_resultList_4_j_idt1268",onLabel:"Alm, Sven Erick ",offLabel:"Alm, Sven Erick ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt1271",{id:"formSmash:items:resultList:4:j_idt1271",widgetVar:"widget_formSmash_items_resultList_4_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Mathematical Statistics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:4:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.Linusson, SvantePrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:4:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Correlations for Paths in Random Orientations of G(n, p) and G(n, m)2011In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 39, no 4, p. 486-506Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:4:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_4_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study random graphs, both G(n, p) and G(n, m), with random orientations on the edges. For three fixed distinct vertices s, a, b we study the correlation, in the combined probability space, of the events {a -> s} and {s -> b}. For G(n, p), we prove that there is a p(c) = 1/2 such that for a fixed p < p(c) the correlation is negative for large enough n and for p > p(c) the correlation is positive for large enough n. We conjecture that for a fixed n >= 27 the correlation changes sign three times for three critical values of p. For G(n, m) it is similarly proved that, with p = m/((n)(2)), there is a critical p(c) that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any l directed edges in G(n, m), is thought to be of independent interest. We present exact recursions to compute P(a -> s) and P(a -> s, s -> b). We also briefly discuss the corresponding question in the quenched version of the problem.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:4:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 6. Alm, Sven Erick PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt1268",{id:"formSmash:items:resultList:5:j_idt1268",widgetVar:"widget_formSmash_items_resultList_5_j_idt1268",onLabel:"Alm, Sven Erick ",offLabel:"Alm, Sven Erick ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt1271",{id:"formSmash:items:resultList:5:j_idt1271",widgetVar:"widget_formSmash_items_resultList_5_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:5:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Linusson, SvantePrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:5:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); First critical probability for a problem on random orientations in G(n,p)2014In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 19, p. 69-Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:5:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_5_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the random graph G (n,p) with a random orientation. For three fixed vertices s, a, b in G(n,p) we study the correlation of the events {a -> s} (there exists a directed path from a to s) and {s -> b}. We prove that asymptotically the correlation is negative for small p, p < C-1/n, where C-1 approximate to 0.3617, positive for C-1/n < p < 2/n and up to p = p(2)(n). Computer aided computations suggest that p(2)(n) = C-2/n, with C-2 approximate to 7.5. We conjecture that the correlation then stays negative for p up to the previously known zero at 1/2; for larger p it is positive.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:5:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 7. Barbour, Andrew et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt1271",{id:"formSmash:items:resultList:6:j_idt1271",widgetVar:"widget_formSmash_items_resultList_6_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:6:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:6:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A functional combinatorial central limit theorem2009In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 14, p. 2352-2370Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:6:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_6_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The paper establishes a functional version of the Hoeffding combinatorial central limit theorem. First, a pre-limiting Gaussian process approximation is defined, and is shown to be at a distance of the order of the Lyapounov ratio from the original random process. Distance is measured by comparison of expectations of smooth functionals of the processes, and the argument is by way of Stein's method. The pre-limiting process is then shown, under weak conditions, to converge to a Gaussian limit process. The theorem is used to describe the shape of random permutation tableaux.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:6:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 8. Blum, Michael et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_7_j_idt1271",{id:"formSmash:items:resultList:7:j_idt1271",widgetVar:"widget_formSmash_items_resultList_7_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:7:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Francois, OlivierJanson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:7:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance2006In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 16, no 4, p. 2195-2214Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_7_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:7:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_7_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); For two decades, the Colless index has been the most frequently used statistic for assessing the balance of phylogenctic trees. In this article, this statistic is studied under the Yule and uniform model of phylogenetic trees. The main tool of analysis is a coupling argument with another well-known index called the Sackin statistic. Asymptotics for the mean, variance and covariance of these two statistics are obtained, as well as their limiting joint distribution for large phylogenies. Under the Yule model, the limiting distribution arises as a solution of a functional fixed point equation. Under the uniform model, the limiting distribution is the Airy distribution. The cornerstone of this study is the fact that the probabilistic models for phylogenetic trees are strongly related to the random permutation and the Catalan models for binary search trees.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:7:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 9. Bollobas, Bela et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt1271",{id:"formSmash:items:resultList:8:j_idt1271",widgetVar:"widget_formSmash_items_resultList_8_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:8:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Gunderson, KarenHolmgren, CeciliaStockholms universitet.Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Przykucki, MichalPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:8:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Bootstrap percolation on Galton-Watson trees2014In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 19, p. 1-27Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:8:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_8_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:8:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 10. Bollobas, Bela et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt1271",{id:"formSmash:items:resultList:9:j_idt1271",widgetVar:"widget_formSmash_items_resultList_9_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:9:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Riordan, OliverPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:9:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Spread-out percolation in R-d2007In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 31, no 2, p. 239-246Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:9:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_9_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Fix

*d*≥ 2, and let*X*be either ℤ^{d}or the points of a Poisson process in ℝ^{d}of intensity 1. Given parameters*r*and*p*, join each pair of points of*X*within distance*r*independently with probability*p*. This is the simplest case of a spread-out percolation model studied by Penrose [Ann Appl Probab 3 (1993) 253276], who showed that, as*r*➝*∞*, the average degree of the corresponding random graph at the percolation threshold tends to 1, i.e., the percolation threshold and the threshold for criticality of the naturally associated branching process approach one another. Here we show that this result follows immediately from of a general result of [3] on inhomogeneous random graphs.PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:9:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 11. Bollobas, Bela PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt1268",{id:"formSmash:items:resultList:10:j_idt1268",widgetVar:"widget_formSmash_items_resultList_10_j_idt1268",onLabel:"Bollobas, Bela ",offLabel:"Bollobas, Bela ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt1271",{id:"formSmash:items:resultList:10:j_idt1271",widgetVar:"widget_formSmash_items_resultList_10_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:10:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Scott, AlexUniv Oxford, Radcliffe Observ Quarter, Math Inst, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:10:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Packing Random Graphs and Hypergraphs2017In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 1, p. 3-13Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:10:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_10_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:10:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 12. Bollobás, Béla et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_11_j_idt1271",{id:"formSmash:items:resultList:11:j_idt1271",widgetVar:"widget_formSmash_items_resultList_11_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:11:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala 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, Analysis and Applied Mathematics.Riordan, OliverPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:11:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Line-of-sight percolation2009In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 18, no 1-2, p. 83-106Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_11_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:11:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_11_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Given omega >= 1, let Z((omega))(2) be the graph with vertex Set Z(2) in which two vertices are joined if they agree in one coordinate and differ by at most omega in the other. (Thus Z((1))(2) is precisely Z(2).) Let p(c)(omega) be the critical probability for site percolation on Z((omega))(2) Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that lim(omega ->infinity) omega p(c)(omega) = log(3/2). We also prove analogues of this result for the n-by-n grid and in higher dimensions, the latter involving interesting connections to Gilbert's continuum percolation model. To prove our results, we explore the component of the origin in a certain non-standard way, and show that this exploration is well approximated by a certain branching random walk.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:11:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 13. Bollobás, Béla et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_12_j_idt1271",{id:"formSmash:items:resultList:12:j_idt1271",widgetVar:"widget_formSmash_items_resultList_12_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:12:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.Riordan, OliverPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:12:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Monotone graph limits and quasimonotone graphs2012In: Internet Mathematics, ISSN 1542-7951, E-ISSN 1944-9488, Vol. 8, p. 187-231Article in journal (Refereed)14. Bollobás, Béla et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_13_j_idt1271",{id:"formSmash:items:resultList:13:j_idt1271",widgetVar:"widget_formSmash_items_resultList_13_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:13:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Riordan, OliverPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:13:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); The phase transition in inhomogeneous random graphs2007In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 31, no 1, p. 3-122Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_13_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:13:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_13_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The "classical" random graph models, in particular G(n,p), are "homogeneous," in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power-law degree distributions. Thus there has been a lot of recent interest in defining and studying "inhomogeneous" random graph models.

One of the most studied properties of these new models is their "robustness", or, equivalently, the "phase transition" as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years.

Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence.

Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n, p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied.

We show that, under one very weak assumption (that the expected number of edges is "what it should be"), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze.

We also consider other properties of the model, showing, for example, that when there is a giant component, it is "stable": for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n).

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:13:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 15. Bousquet-Mélou, Mireille et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt1271",{id:"formSmash:items:resultList:14:j_idt1271",widgetVar:"widget_formSmash_items_resultList_14_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:14:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:14:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); The density of the ISE and local limit laws for embedded trees2006In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 16, no 3, p. 1597-1632Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:14:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_14_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (integrated SuperBrownian excursion). Here, we prove a local version of this result: ISE has a (random) Milder continuous density, and the vertical profile of embedded trees converges to this density, at least for some such trees.

As a consequence, we derive a formula for the distribution of the density of ISE at a given point. This follows from earlier results by Bousquet-Melou on convergence of the vertical profile at a fixed point.

We also provide a recurrence relation defining the moments of the (random) moments of ISE.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:14:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 16. Brightwell, Graham PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt1268",{id:"formSmash:items:resultList:15:j_idt1268",widgetVar:"widget_formSmash_items_resultList_15_j_idt1268",onLabel:"Brightwell, Graham ",offLabel:"Brightwell, Graham ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt1271",{id:"formSmash:items:resultList:15:j_idt1271",widgetVar:"widget_formSmash_items_resultList_15_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); London Sch Econ, Dept Math, London WC2A 2AE, England..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:15:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Luczak, MalwinaQueen Mary Univ London, Sch Math, London, England..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:15:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); The Greedy Independent Set in a Random Graph with Given Degrees2017In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 4, p. 565-586Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:15:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_15_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:15:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 17. Brill, Markus PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt1268",{id:"formSmash:items:resultList:16:j_idt1268",widgetVar:"widget_formSmash_items_resultList_16_j_idt1268",onLabel:"Brill, Markus ",offLabel:"Brill, Markus ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt1271",{id:"formSmash:items:resultList:16:j_idt1271",widgetVar:"widget_formSmash_items_resultList_16_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Univ Oxford, Oxford, England.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:16:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Freeman, RupertDuke Univ, Durham, NC 27706 USA.Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Lackner, MartinUniv Oxford, Oxford, England.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:16:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Phragmen's Voting Methods and Justified Representation2017In: Thirty-First AAAI Conference On Artificial Intelligence, Assoc Advancement Artificial Intelligence , 2017, p. 406-413Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:16:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_16_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); In the late 19th century, Lars Edvard Phragmen proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants-one minimizing the maximal load and one minimizing the variance of loads-and a sequential variant. We study Phragmen's methods from an axiomatic point of view, focussing on justified representation and related properties that have recently been introduced by Aziz et al. (2015a) and Sanchez-Fernandez et al. (2017). We show that the sequential variant satisfies proportional justified representation, making it the first known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmen's methods and provide mixed- integer programming based algorithms for computing them.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:16:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 18. Britton, Tom et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_17_j_idt1271",{id:"formSmash:items:resultList:17:j_idt1271",widgetVar:"widget_formSmash_items_resultList_17_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:17:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.Martin-Löf, AndersPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:17:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Graphs with specified degree distributions, simple epidemics and local vaccination strategies2007Report (Other scientific)19. Britton, Tom et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_18_j_idt1271",{id:"formSmash:items:resultList:18:j_idt1271",widgetVar:"widget_formSmash_items_resultList_18_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:18:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Martin-Löf, AndersPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:18:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Graphs with specified degree distributions, simple epidemics and local vaccination strategies2007In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 39, no 4, p. 922-948Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_18_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:18:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_18_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Consider a random graph, having a prespecified degree distribution F, but other than that being uniformly distributed, describing the social structure (friendship) in a large community. Suppose that one individual in the community is externally infected by an infectious disease and that the disease has its course by assuming that infected individuals infect their not yet infected friends independently with probability p. For this situation, we determine the values of R-0, the basic reproduction number, and tau(0), the asymptotic final size in the case of a major outbreak. Furthermore, we examine some different local vaccination strategies, where individuals are chosen randomly and vaccinated, or friends of the selected individuals are vaccinated, prior to the introduction of the disease. For the studied vaccination strategies, we determine R-v, the reproduction number, and tau(v), the asymptotic final proportion infected in the case of a major outbreak, after vaccinating a fraction v.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:18:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 20. Cai, Xing Shi PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt1268",{id:"formSmash:items:resultList:19:j_idt1268",widgetVar:"widget_formSmash_items_resultList_19_j_idt1268",onLabel:"Cai, Xing Shi ",offLabel:"Cai, Xing Shi ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt1271",{id:"formSmash:items:resultList:19:j_idt1271",widgetVar:"widget_formSmash_items_resultList_19_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:19:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Holmgren, CeciliaUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Johansson, TonyUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Skerman, FionaUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:19:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Inversions in Split Trees and Conditional Galton-Watson Treest2019In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 28, no 3, p. 335-364Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:19:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_19_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:19:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 21. Cai, Xing Shi PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt1268",{id:"formSmash:items:resultList:20:j_idt1268",widgetVar:"widget_formSmash_items_resultList_20_j_idt1268",onLabel:"Cai, Xing Shi ",offLabel:"Cai, Xing Shi ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt1271",{id:"formSmash:items:resultList:20:j_idt1271",widgetVar:"widget_formSmash_items_resultList_20_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:20:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:20:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Non-fringe subtrees in conditioned Galton-Watson trees2018In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 3, article id P3.40Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:20:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_20_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study S(T-n), the number of subtrees in a conditioned Galton-Watson tree of size n. With two very different methods, we show that log(S(T-n)) has a Central Limit Law and that the moments of S(T-n) are of exponential scale.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:20:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 22. Cooper, Colin PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt1268",{id:"formSmash:items:resultList:21:j_idt1268",widgetVar:"widget_formSmash_items_resultList_21_j_idt1268",onLabel:"Cooper, Colin ",offLabel:"Cooper, Colin ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt1271",{id:"formSmash:items:resultList:21:j_idt1271",widgetVar:"widget_formSmash_items_resultList_21_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Univ London, Kings Coll, Dept Comp Sci, London WC2R 2LS, England..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:21:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Frieze, AlanCarnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15217 USA..Ince, NateCarnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15217 USA..Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Spencer, JoelNYU, Courant Inst, New York, NY 10012 USA..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:21:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Length of a Random Minimum Spanning Tree2016In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 25, no 1, p. 89-107Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:21:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_21_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the expected value of the length L-n of the minimum spanning tree of the complete graph K-n when each edge e is given an independent uniform [0, 1] edge weight. We sharpen the result of Frieze [6] that lim(n ->infinity) E(L-n) = zeta(3) and show that E(L-n) = zeta(3) + c(1)/n + c(2) + o(1)/n4/3, where c(1), c(2) are explicitly defined constants.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:21:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 23. Cwikel, Michael et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_22_j_idt1271",{id:"formSmash:items:resultList:22:j_idt1271",widgetVar:"widget_formSmash_items_resultList_22_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:22:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:22:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Complex interpolation of compact operators into the couple (FL^oo,FL_1^oo)2007In: Interpolation Theory and Applications: Conference on Interpolation Theory and Applications in honor of Professor Michael Cwikel, 2007Conference paper (Refereed)24. Devroye, Luc et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt1271",{id:"formSmash:items:resultList:23:j_idt1271",widgetVar:"widget_formSmash_items_resultList_23_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:23:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:23:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Protected nodes and fringe subtrees in some random trees2014In: Electronic Communications in Probability, ISSN 1083-589X, E-ISSN 1083-589X, Vol. 19, p. 1-10Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:23:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_23_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study protected nodes in various classes of random rooted trees by putting them in the general context of fringe subtrees introduced by Aldous (1991). Several types of random trees are considered: simply generated trees (or conditioned Galton-Watson trees), which includes several cases treated separately by other authors, binary search trees and random recursive trees. This gives unified and simple proofs of several earlier results, as well as new results.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:23:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 25. Diaconis, Persi et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_24_j_idt1271",{id:"formSmash:items:resultList:24:j_idt1271",widgetVar:"widget_formSmash_items_resultList_24_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:24:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Holmes, SusanJanson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:24:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Interval Graph Limits2013In: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 17, no 1, p. 27-52Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_24_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:24:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_24_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We work out a graph limit theory for dense interval graphs. The theory developed departs from the usual description of a graph limit as a symmetric function W(x, y) on the unit square, with x and y uniform on the interval (0, 1). Instead, we fix a W and change the underlying distribution of the coordinates x and y. We find choices such that our limits are continuous. Connections to random interval graphs are given, including some examples. We also show a continuity result for the chromatic number and clique number of interval graphs. Some results on uniqueness of the limit description are given for general graph limits.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:24:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 26. Diaconis, Persi PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_25_j_idt1268",{id:"formSmash:items:resultList:25:j_idt1268",widgetVar:"widget_formSmash_items_resultList_25_j_idt1268",onLabel:"Diaconis, Persi ",offLabel:"Diaconis, Persi ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_25_j_idt1271",{id:"formSmash:items:resultList:25:j_idt1271",widgetVar:"widget_formSmash_items_resultList_25_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:25:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:25:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Graph limits and exchangeable random graphs2007Report (Other scientific)27. Diaconis, Persi et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_26_j_idt1271",{id:"formSmash:items:resultList:26:j_idt1271",widgetVar:"widget_formSmash_items_resultList_26_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:26:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.Holmes, SusanPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:26:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Threshold graph limits and random threshold graphs2008In: Internet Mathematics, ISSN 1542-7951, Vol. 5, no 3, p. 267-320Article in journal (Refereed)28. Diaconis, Persi et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_27_j_idt1271",{id:"formSmash:items:resultList:27:j_idt1271",widgetVar:"widget_formSmash_items_resultList_27_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:27:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Rhoades, Robert C.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:27:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Note on a partition limit theorem for rank and crank2013In: Bulletin of the London Mathematical Society, ISSN 0024-6093, E-ISSN 1469-2120, Vol. 45, no 3, p. 551-553Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_27_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:27:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_27_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); If lambda is a partition of n, then the rank rk(lambda) is the size of the largest part minus the number of parts. Under the uniform distribution on partitions, in K. Bringmann, K. Mahlburg, and R. C. Rhoades (Bull. Lond. Math. Soc., 43 (2011) 661-672), it is shown that <inline-graphic xlink:href="BDS121IM1" xmlns:xlink="http://www.w3.org/1999/xlink"/> has a limiting distribution. We identify the limit as the difference between two independent extreme value distributions and as the distribution of beta(T), where beta(t) is standard Brownian motion and T is the first time that an independendent 3-dimensional Brownian motion hits the unit sphere. The same limit holds for the crank.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:27:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 29. Drmota, Michael et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_28_j_idt1271",{id:"formSmash:items:resultList:28:j_idt1271",widgetVar:"widget_formSmash_items_resultList_28_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:28:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.Neininger, RalphPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:28:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A Functional Limit Theorem for The Profile of Search Trees2006Report (Other (popular scientific, debate etc.))30. Ekström, Erik PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt1268",{id:"formSmash:items:resultList:29:j_idt1268",widgetVar:"widget_formSmash_items_resultList_29_j_idt1268",onLabel:"Ekström, Erik ",offLabel:"Ekström, Erik ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt1271",{id:"formSmash:items:resultList:29:j_idt1271",widgetVar:"widget_formSmash_items_resultList_29_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:29:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Hobson, DavidJanson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Tysk, JohanUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:29:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Can time-homogeneous diffusions produce any distribution?2013In: Probability theory and related fields, ISSN 0178-8051, E-ISSN 1432-2064, Vol. 155, no 3-4, p. 493-520Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:29:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_29_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Given a centred distribution, can one find a time-homogeneous martingale diffusion starting at zero which has the given law at time 1? We answer the question affirmatively if generalized diffusions are allowed.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:29:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 31. Ekström, Erik PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt1268",{id:"formSmash:items:resultList:30:j_idt1268",widgetVar:"widget_formSmash_items_resultList_30_j_idt1268",onLabel:"Ekström, Erik ",offLabel:"Ekström, Erik ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt1271",{id:"formSmash:items:resultList:30:j_idt1271",widgetVar:"widget_formSmash_items_resultList_30_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Applied Mathematics and Statistics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:30:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:30:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); The inverse first-passage problem and optimal stopping2016In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 26, no 5, p. 3154-3177Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:30:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_30_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:30:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 32. Ekström, Erik PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt1268",{id:"formSmash:items:resultList:31:j_idt1268",widgetVar:"widget_formSmash_items_resultList_31_j_idt1268",onLabel:"Ekström, Erik ",offLabel:"Ekström, Erik ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt1271",{id:"formSmash:items:resultList:31:j_idt1271",widgetVar:"widget_formSmash_items_resultList_31_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:31:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Tysk, JohanUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:31:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Feynman-Kac Theorems for Generalized Diffusions2015In: Transactions of the American Mathematical Society, ISSN 0002-9947, E-ISSN 1088-6850, Vol. 367, no 11, p. 8051-8070, article id PII S0002-9947(2015)06278-3Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:31:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_31_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We find Feynman-Kac type representation theorems for generalized diffusions. To do this we need to establish existence, uniqueness and regularity results for equations with measure-valued coefficients.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:31:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 33. Ekström, Erik PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_32_j_idt1268",{id:"formSmash:items:resultList:32:j_idt1268",widgetVar:"widget_formSmash_items_resultList_32_j_idt1268",onLabel:"Ekström, Erik ",offLabel:"Ekström, Erik ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_32_j_idt1271",{id:"formSmash:items:resultList:32:j_idt1271",widgetVar:"widget_formSmash_items_resultList_32_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:32:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.Tysk, JohanUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:32:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Superreplication of options on several underlying assets2003Report (Other scientific)34. Ekström, Erik PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_33_j_idt1268",{id:"formSmash:items:resultList:33:j_idt1268",widgetVar:"widget_formSmash_items_resultList_33_j_idt1268",onLabel:"Ekström, Erik ",offLabel:"Ekström, Erik ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_33_j_idt1271",{id:"formSmash:items:resultList:33:j_idt1271",widgetVar:"widget_formSmash_items_resultList_33_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:33:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Tysk, JohanUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:33:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Superreplication of options on several underlying assets2005In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 42, no 1, p. 27-38Article in journal (Refereed)35. Fill, James Allen et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_34_j_idt1271",{id:"formSmash:items:resultList:34:j_idt1271",widgetVar:"widget_formSmash_items_resultList_34_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:34:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:34:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Precise logarithmic asymptotics for the right tails of some limit random variables for random trees2009In: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 12, no 4, p. 403-416Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_34_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:34:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_34_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i) that the random variables we study can be represented as functionals of a Brownian excursion and (ii) that a large deviation principle with good rate function is known explicitly for Brownian excursion. Examples include limit distributions of the total path length and of the Wiener index in conditioned Galton-Watson trees (also known as simply generated trees). In the case of Wiener index (where we recover results proved by Svante Janson and Philippe Chassaing by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the constant's precise value remains unknown.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:34:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 36. Fill, James Allen et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_35_j_idt1271",{id:"formSmash:items:resultList:35:j_idt1271",widgetVar:"widget_formSmash_items_resultList_35_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:35:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:35:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); The number of bit comparisons used by Quicksort: an average-case analysis2012In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 17, p. 43-Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_35_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:35:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_35_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit comparisons. On the other hand, the standard analyses of many other algorithms (such as Quicksort) are performed in terms of the number of key comparisons. We introduce the prospect of a fair comparison between algorithms of the two types by providing an average-case analysis of the number of bit comparisons required by Quicksort. Counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total. We also provide a new algorithm, "BitsQuick", that reduces this factor to constant order by eliminating needless bit comparisons.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:35:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 37. Fill, James Allen et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_36_j_idt1271",{id:"formSmash:items:resultList:36:j_idt1271",widgetVar:"widget_formSmash_items_resultList_36_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:36:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.Ward, Mark DanielPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:36:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Partitions with Distinct Multiplicities of Parts: On An "Unsolved Problem" Posed By Herbert Wilf2012In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 2, p. P18-Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_36_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:36:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_36_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Wilf's Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different. We refer to these as Wilf partitions. Using f(n) to denote the number of Wilf partitions,we establish lead-order asymptotics for ln f(n).

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:36:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 38. Fill, Jim et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_37_j_idt1271",{id:"formSmash:items:resultList:37:j_idt1271",widgetVar:"widget_formSmash_items_resultList_37_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:37:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:37:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Precise logarithmic asymptotics for the right tails of some limit random variables for random trees2007Report (Other scientific)39. Gravier, Sylvain et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt1271",{id:"formSmash:items:resultList:38:j_idt1271",widgetVar:"widget_formSmash_items_resultList_38_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:38:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Laihonen, TeroRanto, SannaPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:38:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Graphs where every k-subset of vertices is an identifying set2014In: DISCRETE MATH THEOR, ISSN 1462-7264, Vol. 16, no 1, p. 73-88Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:38:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_38_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Let G = ( V, E) be an undirected graph without loops and multiple edges. A subset C subset of V is called identifying if for every vertex x is an element of V the intersection of C and the closed neighbourhood of x is nonempty, and these intersections are different for different vertices x. Let k be a positive integer. We will consider graphs where every k-subset is identifying. We prove that for every k > 1 the maximal order of such a graph is at most 2k - 2. Constructions attaining the maximal order are given for infinitely many values of k : The corresponding problem of k-subsets identifying any at most l vertices is considered as well.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:38:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 40. Grimmet, Geoffrey et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_39_j_idt1271",{id:"formSmash:items:resultList:39:j_idt1271",widgetVar:"widget_formSmash_items_resultList_39_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:39:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematical Statistics.Scudo, Petra F.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:39:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Weak limits for quantum random walks2003Report (Other scientific)41. Grimmett, Geoffrey et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_40_j_idt1271",{id:"formSmash:items:resultList:40:j_idt1271",widgetVar:"widget_formSmash_items_resultList_40_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:40:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:40:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Random even graphs2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 1, p. R46-Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_40_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:40:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_40_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study a random even subgraph of a finite graph G with a general edge-weight p is an element of (0, 1). We demonstrate how it may be obtained from a certain random-cluster measure on G, and we propose a sampling algorithm based on coupling from the past. A random even subgraph of a planar lattice undergoes a phase transition at the parameter-value 1/2p(c), where p(c) is the critical point of the q = 2 random-cluster model on the dual lattice. The properties of such a graph are discussed, and are related to Schramm-Lowner evolutions (SLE).

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:40:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 42. Grimmett, Geoffrey et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_41_j_idt1271",{id:"formSmash:items:resultList:41:j_idt1271",widgetVar:"widget_formSmash_items_resultList_41_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:41:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:41:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Random even graphs and the Ising model2007Report (Other scientific)43. Grimmett, Geoffrey et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_42_j_idt1271",{id:"formSmash:items:resultList:42:j_idt1271",widgetVar:"widget_formSmash_items_resultList_42_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:42:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics, Mathematics I -V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:42:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Random graphs with forbidden vertex degrees2007Report (Other scientific)44. Hatami, Hamed PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt1268",{id:"formSmash:items:resultList:43:j_idt1268",widgetVar:"widget_formSmash_items_resultList_43_j_idt1268",onLabel:"Hatami, Hamed ",offLabel:"Hatami, Hamed ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt1271",{id:"formSmash:items:resultList:43:j_idt1271",widgetVar:"widget_formSmash_items_resultList_43_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); McGill Univ, Sch Comp Sci, Montreal, PQ, Canada..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:43:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.Szegedy, BalazsUniv Toronto, Dept Math, St George St 40, Toronto, ON M5R 2E4, Canada..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:43:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Graph properties, graph limits, and entropy2018In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 87, no 2, p. 208-229Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:43:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_43_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:43:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 45. Hitczenko, Pawel et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_44_j_idt1271",{id:"formSmash:items:resultList:44:j_idt1271",widgetVar:"widget_formSmash_items_resultList_44_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:44:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:44:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Weighted Random Staircase Tableaux2014In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 23, no 6, p. 1114-1147Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_44_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:44:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_44_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); This paper concerns a relatively new combinatorial structure called staircase tableaux. They were introduced in the context of the asymmetric exclusion process and Askey-Wilson polynomials; however, their purely combinatorial properties have gained considerable interest in the past few years. In this paper we further study combinatorial properties of staircase tableaux. We consider a general model of random staircase tableaux in which symbols (Greek letters) that appear in staircase tableaux may have arbitrary positive weights. (We consider only the case with the parameters u = q = 1.) Under this general model we derive a number of results. Some of our results concern the limiting laws for the number of appearances of symbols in a random staircase tableaux. They generalize and subsume earlier results that were obtained for specific values of the weights. One advantage of our generality is that we may let the weights approach extreme values of zero or infinity, which covers further special cases appearing earlier in the literature. Furthermore, our generality allows us to analyse the structure of random staircase tableaux, and we obtain several results in this direction. One of the tools we use is the generating functions of the parameters of interest. This leads us to a two-parameter family of polynomials, generalizing the classical Eulerian polynomials. We also briefly discuss the relation of staircase tableaux to the asymmetric exclusion process, to other recently introduced types of tableaux, and to an urn model studied by a number of researchers, including Philippe Flajolet.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:44:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 46. Holmgren, Cecilia PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt1268",{id:"formSmash:items:resultList:45:j_idt1268",widgetVar:"widget_formSmash_items_resultList_45_j_idt1268",onLabel:"Holmgren, Cecilia ",offLabel:"Holmgren, Cecilia ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt1271",{id:"formSmash:items:resultList:45:j_idt1271",widgetVar:"widget_formSmash_items_resultList_45_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Stockholms universitet.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:45:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:45:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Asymptotic distribution of two-protected nodes in ternary search trees2015In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 20, article id 9Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:45:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_45_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:45:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 47. Holmgren, Cecilia PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt1268",{id:"formSmash:items:resultList:46:j_idt1268",widgetVar:"widget_formSmash_items_resultList_46_j_idt1268",onLabel:"Holmgren, Cecilia ",offLabel:"Holmgren, Cecilia ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt1271",{id:"formSmash:items:resultList:46:j_idt1271",widgetVar:"widget_formSmash_items_resultList_46_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:46:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:46:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Fringe trees, Crump-Mode-Jagers branching processes and*m*-ary search trees2017In: Probability Surveys, ISSN 1549-5787, E-ISSN 1549-5787, Vol. 14, p. 53-154Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:46:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_46_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:46:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 48. Holmgren, Cecilia PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt1268",{id:"formSmash:items:resultList:47:j_idt1268",widgetVar:"widget_formSmash_items_resultList_47_j_idt1268",onLabel:"Holmgren, Cecilia ",offLabel:"Holmgren, Cecilia ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt1271",{id:"formSmash:items:resultList:47:j_idt1271",widgetVar:"widget_formSmash_items_resultList_47_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Stockholms universitet.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:47:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:47:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Limit laws for functions of fringe trees for binary search trees and random recursive trees2015In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 20, article id 4Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:47:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_47_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:47:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 49. Holmgren, Cecilia PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt1268",{id:"formSmash:items:resultList:48:j_idt1268",widgetVar:"widget_formSmash_items_resultList_48_j_idt1268",onLabel:"Holmgren, Cecilia ",offLabel:"Holmgren, Cecilia ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt1271",{id:"formSmash:items:resultList:48:j_idt1271",widgetVar:"widget_formSmash_items_resultList_48_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:48:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.Sileikis, MatasCharles Univ Prague, Fac Math & Phys, Dept Appl Math, Malostranske Nam 25, CR-11800 Prague, Czech Republic..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:48:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees2017In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 2, article id P2.51Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:48:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_48_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); 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.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:48:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 50. Hwang, Hsien-Kuei PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_49_j_idt1268",{id:"formSmash:items:resultList:49:j_idt1268",widgetVar:"widget_formSmash_items_resultList_49_j_idt1268",onLabel:"Hwang, Hsien-Kuei ",offLabel:"Hwang, Hsien-Kuei ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_49_j_idt1271",{id:"formSmash:items:resultList:49:j_idt1271",widgetVar:"widget_formSmash_items_resultList_49_j_idt1271",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Acad Sinica, Inst Stat Sci, Taipei, Taiwan.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:49:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Janson, SvanteUppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:49:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A central limit theorem for random ordered factorizations of integers2011In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 16, p. 347-361Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_49_j_idt1306_0_j_idt1307",{id:"formSmash:items:resultList:49:j_idt1306:0:j_idt1307",widgetVar:"widget_formSmash_items_resultList_49_j_idt1306_0_j_idt1307",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Write an integer as finite products of ordered factors belonging to a given subset P of integers larger than one. A very general central limit theorem is derived for the number of ordered factors in random factorizations for any subset P containing at least two elements. The method of proof is very simple and relies in part on Delange's Tauberian theorems and an interesting Tauberian technique for handling Dirichlet series associated with odd centered moments.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:49:j_idt1306:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500});

CiteExportLink to result list
http://uu.diva-portal.org/smash/resultList.jsf?query=&language=en&searchType=SIMPLE&noOfRows=50&sortOrder=author_sort_asc&sortOrder2=title_sort_asc&onlyFullText=false&sf=all&aq=%5B%5B%7B%22personId%22%3A%22authority-person%3A12438%22%7D%5D%5D&aqe=%5B%5D&aq2=%5B%5B%5D%5D&af=%5B%5D $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_lower_j_idt1586_recordPermLink",{id:"formSmash:lower:j_idt1586:recordPermLink",widgetVar:"widget_formSmash_lower_j_idt1586_recordPermLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1586_j_idt1588",{id:"formSmash:lower:j_idt1586:j_idt1588",widgetVar:"widget_formSmash_lower_j_idt1586_j_idt1588",target:"formSmash:lower:j_idt1586:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Cite

Citation styleapa ieee modern-language-association vancouver Other style $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt1604",{id:"formSmash:lower:j_idt1604",widgetVar:"widget_formSmash_lower_j_idt1604",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:lower:j_idt1604",e:"change",f:"formSmash",p:"formSmash:lower:j_idt1604",u:"formSmash:lower:otherStyle"},ext);}}});});

- apa
- ieee
- modern-language-association
- vancouver
- Other style

Languagede-DE en-GB en-US fi-FI nn-NO nn-NB sv-SE Other locale $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt1615",{id:"formSmash:lower:j_idt1615",widgetVar:"widget_formSmash_lower_j_idt1615",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:lower:j_idt1615",e:"change",f:"formSmash",p:"formSmash:lower:j_idt1615",u:"formSmash:lower:otherLanguage"},ext);}}});});

- de-DE
- en-GB
- en-US
- fi-FI
- nn-NO
- nn-NB
- sv-SE
- Other locale

Output formathtml text asciidoc rtf $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt1625",{id:"formSmash:lower:j_idt1625",widgetVar:"widget_formSmash_lower_j_idt1625"});});

- html
- text
- asciidoc
- rtf