39 Search Results for "Fill, James Allen"


Volume

LIPIcs, Volume 110

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

AofA 2018, June 25-29, 2018, Uppsala, Sweden

Editors: James Allen Fill and Mark Daniel Ward

Document
Complete Volume
LIPIcs, Volume 110, AofA'18, Complete Volume

Authors: James Allen Fill and Mark Daniel Ward

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
LIPIcs, Volume 110, AofA'18, Complete Volume

Cite as

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Proceedings{fill_et_al:LIPIcs.AofA.2018,
  title =	{{LIPIcs, Volume 110, AofA'18, Complete Volume}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018},
  URN =		{urn:nbn:de:0030-drops-92453},
  doi =		{10.4230/LIPIcs.AofA.2018},
  annote =	{Keywords: Mathematics of computing, Theory of computation, Computing methodologies, Philosophical/theoretical foundations of artificial intelligence}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James Allen Fill and Mark Daniel Ward

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{fill_et_al:LIPIcs.AofA.2018.0,
  author =	{Fill, James Allen and Ward, Mark Daniel},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{0:i--0:xi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.0},
  URN =		{urn:nbn:de:0030-drops-88930},
  doi =		{10.4230/LIPIcs.AofA.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Flajolet Award Lecture
OMG: GW, CLT, CRT and CFTP (Flajolet Award Lecture)

Authors: Luc Devroye

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
After a brief review of the main results on Galton-Watson trees from the past two decades, we will discuss a few recent results in the field.

Cite as

Luc Devroye. OMG: GW, CLT, CRT and CFTP (Flajolet Award Lecture). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{devroye:LIPIcs.AofA.2018.1,
  author =	{Devroye, Luc},
  title =	{{OMG: GW, CLT, CRT and CFTP}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.1},
  URN =		{urn:nbn:de:0030-drops-88943},
  doi =		{10.4230/LIPIcs.AofA.2018.1},
  annote =	{Keywords: Galton-Watson trees, applied probability, asymptotics, simply generated trees}
}
Document
Keynote Speakers
Assumptionless Bounds for Random Trees (Keynote Speakers)

Authors: Louigi Addario-Berry

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Let T be any Galton-Watson tree. Write vol(T) for the volume of T (the number of nodes), ht(T) for the height of T (the greatest distance of any node from the root) and wid(T) for the width of T (the greatest number of nodes at any level). We study the relation between vol(T), ht(T) and wid(T). In the case when the offspring distribution p = (p_i, i >= 0) has mean one and finite variance, both ht(T) and wid(T) are typically of order vol(T)^{1/2}, and have sub-Gaussian upper tails on this scale. Heuristically, as the tail of the offspring distribution becomes heavier, the tree T becomes "shorter and bushier". I will describe a collection of work which can be viewed as justifying this heuristic in various ways In particular, I will explain how classical bounds on Lévy's concentration function for random walks may be used to show that for any offspring distribution, the random variable ht(T)/wid(T) has sub-exponential tails. I will also describe a more combinatorial approach to coupling random trees with different degree sequences which allows the heights of randomly sampled vertices to be compared.

Cite as

Louigi Addario-Berry. Assumptionless Bounds for Random Trees (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{addarioberry:LIPIcs.AofA.2018.2,
  author =	{Addario-Berry, Louigi},
  title =	{{Assumptionless Bounds for Random Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.2},
  URN =		{urn:nbn:de:0030-drops-88951},
  doi =		{10.4230/LIPIcs.AofA.2018.2},
  annote =	{Keywords: Random trees, simply generated trees}
}
Document
Keynote Speakers
Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers)

Authors: Béla Bollobás

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Since the advent of fast computers, much attention has been paid to practical factoring algorithms. Several of these algorithms set out to find two squares x^2, y^2 that are congruent modulo the number n we wish to factor, and are non-trivial in the sense that x is not equivalent to +/- y mod n. In 1994, this prompted Pomerance to ask the following question. Let a_1, a_2, ... be random integers, chosen independently and uniformly from a set {1, ... x}. Let N be the smallest index such that {a_1, ... , a_N} contains a subsequence, the product of whose elements is a perfect square. What can you say about this random number N? In particular, give bounds N_0 and N_1 such that P(N_0 <= N <= N_1)-> 1 as x -> infty. Pomerance also gave bounds N_0 and N_1 with log N_0 ~ log N_1. In 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds of Pomerance, bringing them within a constant of each other, and conjectured that their upper bound is sharp. In a recent paper, Paul Balister, Rob Morris and I have proved this conjecture. In the talk I shall review some related results and sketch some of the ideas used in our proof.

Cite as

Béla Bollobás. Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bollobas:LIPIcs.AofA.2018.3,
  author =	{Bollob\'{a}s, B\'{e}la},
  title =	{{Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.3},
  URN =		{urn:nbn:de:0030-drops-88967},
  doi =		{10.4230/LIPIcs.AofA.2018.3},
  annote =	{Keywords: integer factorization, perfect square, random graph process}
}
Document
Keynote Speakers
Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers)

Authors: Karen Gunderson

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
A bootstrap process is a type of cellular automaton, acting on the vertices of a graph which are in one of two states: `healthy' or `infected'. For any positive integer r, the r-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least r infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected. For an infinite graph, of interest is the random setting, in which each vertex is initially infected independently with a fixed probability. I will give some history of this process for infinite trees and present results on the possible values of critical probabilities for percolation on Galton-Watson trees. This talk is based on joint work with Bollobás, Holmgren, Janson, and Przykucki.

Cite as

Karen Gunderson. Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{gunderson:LIPIcs.AofA.2018.4,
  author =	{Gunderson, Karen},
  title =	{{Bootstrap Percolation and Galton-Watson Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.4},
  URN =		{urn:nbn:de:0030-drops-88977},
  doi =		{10.4230/LIPIcs.AofA.2018.4},
  annote =	{Keywords: bootstrap percolation, Galton-Watson trees}
}
Document
Keynote Speakers
Thinking in Advance About the Last Algorithm We Ever Need to Invent (Keynote Speakers)

Authors: Olle Häggström

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We survey current discussions about possibilities and risks associated with an artificial intelligence breakthrough on the level that puts humanity in the situation where we are no longer foremost on the planet in terms of general intelligence. The importance of thinking in advance about such an event is emphasized. Key issues include when and how suddenly superintelligence is likely to emerge, the goals and motivations of a superintelligent machine, and what we can do to improve the chances of a favorable outcome.

Cite as

Olle Häggström. Thinking in Advance About the Last Algorithm We Ever Need to Invent (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{haggstrom:LIPIcs.AofA.2018.5,
  author =	{H\"{a}ggstr\"{o}m, Olle},
  title =	{{Thinking in Advance About the Last Algorithm We Ever Need to Invent}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.5},
  URN =		{urn:nbn:de:0030-drops-88982},
  doi =		{10.4230/LIPIcs.AofA.2018.5},
  annote =	{Keywords: intelligence explosion, Omohundro-Bostrom theory, superintelligence}
}
Document
Keynote Speakers
Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers)

Authors: Svante Janson

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Consider a random permutation drawn from the set of permutations of length n that avoid a given set of one or several patterns of length 3. We show that the number of occurrences of another pattern has a limit distribution, after suitable scaling. In several cases, the limit is normal, as it is in the case of unrestricted random permutations; in other cases the limit is a non-normal distribution, depending on the studied pattern. In the case when a single pattern of length 3 is forbidden, the limit distributions can be expressed in terms of a Brownian excursion. The analysis is made case by case; unfortunately, no general method is known, and no general pattern emerges from the results.

Cite as

Svante Janson. Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{janson:LIPIcs.AofA.2018.6,
  author =	{Janson, Svante},
  title =	{{Patterns in Random Permutations Avoiding Some Other Patterns}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.6},
  URN =		{urn:nbn:de:0030-drops-88996},
  doi =		{10.4230/LIPIcs.AofA.2018.6},
  annote =	{Keywords: Random permutations, patterns, forbidden patterns, limit in distribution, U-statistics}
}
Document
Keynote Speakers
Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers)

Authors: Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We consider k-dimensional random simplicial complexes that are generated from the binomial random (k+1)-uniform hypergraph by taking the downward-closure, where k >= 2. For each 1 <= j <= k-1, we determine when all cohomology groups with coefficients in F_2 from dimension one up to j vanish and the zero-th cohomology group is isomorphic to F_2. This property is not monotone, but nevertheless we show that it has a single sharp threshold. Moreover, we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. Furthermore, we study the asymptotic distribution of the dimension of the j-th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced in [Linial and Meshulam, Combinatorica, 2006], a result which has only been known for dimension two [Kahle and Pittel, Random Structures Algorithms, 2016].

Cite as

Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel. Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{cooley_et_al:LIPIcs.AofA.2018.7,
  author =	{Cooley, Oliver and Del Giudice, Nicola and Kang, Mihyun and Spr\"{u}ssel, Philipp},
  title =	{{Vanishing of Cohomology Groups of Random Simplicial Complexes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.7},
  URN =		{urn:nbn:de:0030-drops-89006},
  doi =		{10.4230/LIPIcs.AofA.2018.7},
  annote =	{Keywords: Random hypergraphs, random simplicial complexes, sharp threshold, hitting time, connectedness}
}
Document
Keynote Speakers
Periods in Subtraction Games (Keynote Speakers)

Authors: Bret Benesh, Jamylle Carter, Deidra A. Coleman, Douglas G. Crabill, Jack H. Good, Michael A. Smith, Jennifer Travis, and Mark Daniel Ward

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We discuss the structure of periods in subtraction games. In particular, we discuss ways that a computational approach yields insights to the periods that emerge in the asymptotic structure of these combinatorial games.

Cite as

Bret Benesh, Jamylle Carter, Deidra A. Coleman, Douglas G. Crabill, Jack H. Good, Michael A. Smith, Jennifer Travis, and Mark Daniel Ward. Periods in Subtraction Games (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 8:1-8:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{benesh_et_al:LIPIcs.AofA.2018.8,
  author =	{Benesh, Bret and Carter, Jamylle and Coleman, Deidra A. and Crabill, Douglas G. and Good, Jack H. and Smith, Michael A. and Travis, Jennifer and Ward, Mark Daniel},
  title =	{{Periods in Subtraction Games}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{8:1--8:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.8},
  URN =		{urn:nbn:de:0030-drops-89015},
  doi =		{10.4230/LIPIcs.AofA.2018.8},
  annote =	{Keywords: combinatorial games, subtraction games, periods, asymptotic structure}
}
Document
Permutations in Binary Trees and Split Trees

Authors: Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We investigate the number of permutations that occur in random node labellings of trees. This is a generalisation of the number of subpermutations occuring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees [Cai et al., 2017]. We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye [Devroye, 1998]. Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree with high probability the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.

Cite as

Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman. Permutations in Binary Trees and Split Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.AofA.2018.9,
  author =	{Albert, Michael and Holmgren, Cecilia and Johansson, Tony and Skerman, Fiona},
  title =	{{Permutations in Binary Trees and Split Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.9},
  URN =		{urn:nbn:de:0030-drops-89025},
  doi =		{10.4230/LIPIcs.AofA.2018.9},
  annote =	{Keywords: random trees, split trees, permutations, inversions, cumulant}
}
Document
Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem

Authors: Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
In a companion article dedicated to the enumeration aspects, we showed how to obtain closed form formulas for the generating functions of walks, bridges, meanders, and excursions avoiding any fixed word (a pattern p). The autocorrelation polynomial of this forbidden pattern p (as introduced by Guibas and Odlyzko in 1981, in the context of regular expressions) plays a crucial role. In this article, we get the asymptotics of these walks. We also introduce a trivariate generating function (length, final altitude, number of occurrences of p), for which we derive a closed form. We prove that the number of occurrences of p is normally distributed: This is what Flajolet and Sedgewick call an instance of Borges's theorem. We thus extend and refine the study by Banderier and Flajolet in 2002 on lattice paths, and we unify several dozens of articles which investigated patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. Our approach relies on methods of analytic combinatorics, and on a matricial generalization of the kernel method. The situation is much more involved than in the Banderier-Flajolet work: forbidden patterns lead to a wider zoology of asymptotic behaviours, and we classify them according to the geometry of a Newton polygon associated with these constrained walks, and we analyse what are the universal phenomena common to all these models of lattice paths avoiding a pattern.

Cite as

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{asinowski_et_al:LIPIcs.AofA.2018.10,
  author =	{Asinowski, Andrei and Bacher, Axel and Banderier, Cyril and Gittenberger, Bernhard},
  title =	{{Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89035},
  doi =		{10.4230/LIPIcs.AofA.2018.10},
  annote =	{Keywords: Lattice paths, pattern avoidance, finite automata, context-free languages, autocorrelation, generating function, kernel method, asymptotic analysis, Gaussian limit law}
}
Document
Periodic Pólya Urns and an Application to Young Tableaux

Authors: Cyril Banderier, Philippe Marchal, and Michael Wallner

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.

Cite as

Cyril Banderier, Philippe Marchal, and Michael Wallner. Periodic Pólya Urns and an Application to Young Tableaux. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2018.11,
  author =	{Banderier, Cyril and Marchal, Philippe and Wallner, Michael},
  title =	{{Periodic P\'{o}lya Urns and an Application to Young Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.11},
  URN =		{urn:nbn:de:0030-drops-89045},
  doi =		{10.4230/LIPIcs.AofA.2018.11},
  annote =	{Keywords: P\'{o}lya urn, Young tableau, generating functions, analytic combinatorics, pumping moment, D-finite function, hypergeometric function, generalized Gamma distribution, Mittag-Leffler distribution}
}
Document
Diagonal Asymptotics for Symmetric Rational Functions via ACSV

Authors: Yuliy Baryshnikov, Stephen Melczer, Robin Pemantle, and Armin Straub

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We consider asymptotics of power series coefficients of rational functions of the form 1/Q where Q is a symmetric multilinear polynomial. We review a number of such cases from the literature, chiefly concerned either with positivity of coefficients or diagonal asymptotics. We then analyze coefficient asymptotics using ACSV (Analytic Combinatorics in Several Variables) methods. While ACSV sometimes requires considerable overhead and geometric computation, in the case of symmetric multilinear rational functions there are some reductions that streamline the analysis. Our results include diagonal asymptotics across entire classes of functions, for example the general 3-variable case and the Gillis-Reznick-Zeilberger (GRZ) case, where the denominator in terms of elementary symmetric functions is 1 - e_1 + c e_d in any number d of variables. The ACSV analysis also explains a discontinuous drop in exponential growth rate for the GRZ class at the parameter value c = (d-1)^{d-1}, previously observed for d=4 only by separately computing diagonal recurrences for critical and noncritical values of c.

Cite as

Yuliy Baryshnikov, Stephen Melczer, Robin Pemantle, and Armin Straub. Diagonal Asymptotics for Symmetric Rational Functions via ACSV. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{baryshnikov_et_al:LIPIcs.AofA.2018.12,
  author =	{Baryshnikov, Yuliy and Melczer, Stephen and Pemantle, Robin and Straub, Armin},
  title =	{{Diagonal Asymptotics for Symmetric Rational Functions via ACSV}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.12},
  URN =		{urn:nbn:de:0030-drops-89055},
  doi =		{10.4230/LIPIcs.AofA.2018.12},
  annote =	{Keywords: Analytic combinatorics, generating function, coefficient, lacuna, positivity, Morse theory, D-finite, smooth point}
}
  • Refine by Author
  • 3 Fill, James Allen
  • 3 Johansson, Tony
  • 3 Kang, Mihyun
  • 3 Skerman, Fiona
  • 3 Ward, Mark Daniel
  • Show More...

  • Refine by Classification
  • 11 Mathematics of computing → Enumeration
  • 10 Mathematics of computing → Generating functions
  • 5 Mathematics of computing → Random graphs
  • 5 Mathematics of computing → Trees
  • 5 Theory of computation → Random walks and Markov chains
  • Show More...

  • Refine by Keyword
  • 5 Galton-Watson trees
  • 3 central limit theorem
  • 3 generating functions
  • 3 singularity analysis
  • 2 Analytic combinatorics
  • Show More...

  • Refine by Type
  • 38 document
  • 1 volume

  • Refine by Publication Year
  • 39 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail