Volume
LIPIcs, Volume 110
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Event
AofA 2018, June 25-29, 2018, Uppsala, SwedenEditors
Publication Details
- published at: 2018-06-18
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-078-1
- DBLP: db/conf/aofa/aofa2018
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 110, AofA'18, Complete Volume
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.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
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.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)
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.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)
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.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)
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.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)
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.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)
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.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)
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)
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.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)
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.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
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.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
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.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
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.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
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.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}
}
Document
Asymptotic Distribution of Parameters in Random Maps
Abstract
We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.
Cite as
Olivier Bodini, Julien Courtiel, Sergey Dovgal, and Hsien-Kuei Hwang. Asymptotic Distribution of Parameters in Random Maps. 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. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bodini_et_al:LIPIcs.AofA.2018.13,
author = {Bodini, Olivier and Courtiel, Julien and Dovgal, Sergey and Hwang, Hsien-Kuei},
title = {{Asymptotic Distribution of Parameters in Random Maps}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {13:1--13: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.13},
URN = {urn:nbn:de:0030-drops-89069},
doi = {10.4230/LIPIcs.AofA.2018.13},
annote = {Keywords: Random maps, Analytic combinatorics, Rooted Maps, Beta law, Limit laws, Patterns, Generating functions, Riccati equation}
}
Document
Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes
Abstract
In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process is a directed acyclic graph (DAG). Since the quantitative study of increasingly labeled DAG (directly related to processes) seems out of reach (this is a #P-complete problem), we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the classical sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of a uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.
Cite as
Olivier Bodini, Matthieu Dien, Antoine Genitrini, and Alfredo Viola. Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes. 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. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bodini_et_al:LIPIcs.AofA.2018.14,
author = {Bodini, Olivier and Dien, Matthieu and Genitrini, Antoine and Viola, Alfredo},
title = {{Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {14:1--14: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.14},
URN = {urn:nbn:de:0030-drops-89075},
doi = {10.4230/LIPIcs.AofA.2018.14},
annote = {Keywords: Concurrency Theory, Future, Uniform Random Sampling, Unranking, Analytic Combinatorics}
}
Document
Inversions in Split Trees and Conditional Galton-Watson Trees
Abstract
We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. 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. For T_n being split trees [Devroye, 1999], 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. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].
Cite as
Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman. Inversions in Split Trees and Conditional Galton-Watson 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. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cai_et_al:LIPIcs.AofA.2018.15,
author = {Cai, Xing Shi and Holmgren, Cecilia and Janson, Svante and Johansson, Tony and Skerman, Fiona},
title = {{Inversions in Split Trees and Conditional Galton-Watson Trees}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {15:1--15: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.15},
URN = {urn:nbn:de:0030-drops-89085},
doi = {10.4230/LIPIcs.AofA.2018.15},
annote = {Keywords: inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant}
}
Document
The Cover Time of a Biased Random Walk on a Random Cubic Graph
Abstract
We study a random walk that prefers to use unvisited edges in the context of random cubic graphs, i.e., graphs chosen uniformly at random from the set of 3-regular graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being n log n and 3/2 n log n respectively.
Cite as
Colin Cooper, Alan Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. 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. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cooper_et_al:LIPIcs.AofA.2018.16,
author = {Cooper, Colin and Frieze, Alan and Johansson, Tony},
title = {{The Cover Time of a Biased Random Walk on a Random Cubic Graph}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {16:1--16: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.16},
URN = {urn:nbn:de:0030-drops-89097},
doi = {10.4230/LIPIcs.AofA.2018.16},
annote = {Keywords: Random walk, random regular graph, cover time}
}
Document
The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property
Abstract
We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which `region' m falls into.
Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases.
In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n.
We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.
Cite as
Chris Dowden, Mihyun Kang, and Michael Krivelevich. The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property. 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. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dowden_et_al:LIPIcs.AofA.2018.17,
author = {Dowden, Chris and Kang, Mihyun and Krivelevich, Michael},
title = {{The Genus of the Erd\"{o}s-R\'{e}nyi Random Graph and the Fragile Genus Property}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {17:1--17: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.17},
URN = {urn:nbn:de:0030-drops-89100},
doi = {10.4230/LIPIcs.AofA.2018.17},
annote = {Keywords: Random graphs, Genus, Fragile genus}
}
Document
Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes
Abstract
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in series-parallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.
Cite as
Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué. Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes. 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. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{drmota_et_al:LIPIcs.AofA.2018.18,
author = {Drmota, Michael and Ramos, Lander and Requil\'{e}, Cl\'{e}ment and Ru\'{e}, Juanjo},
title = {{Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {18:1--18: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.18},
URN = {urn:nbn:de:0030-drops-89117},
doi = {10.4230/LIPIcs.AofA.2018.18},
annote = {Keywords: Asymptotic enumeration, central limit laws, subcritical graph classes, maximal independent set, maximal matching}
}
Document
The Number of Double Triangles in Random Planar Maps
Abstract
The purpose of this paper is to provide a central limit theorem for the number of occurrences of double triangles in random planar maps. This is the first result of this kind that goes beyond face counts of given valency. The method is based on generating functions, an involved combinatorial decomposition scheme that leads to a system of catalytic functional equations and an analytic extension of the Quadratic Method to systems of equations.
Cite as
Michael Drmota and Guan-Ru Yu. The Number of Double Triangles in Random Planar Maps. 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. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{drmota_et_al:LIPIcs.AofA.2018.19,
author = {Drmota, Michael and Yu, Guan-Ru},
title = {{The Number of Double Triangles in Random Planar Maps}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {19:1--19:18},
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.19},
URN = {urn:nbn:de:0030-drops-89120},
doi = {10.4230/LIPIcs.AofA.2018.19},
annote = {Keywords: Planar maps, pattern occuence, generating functions, quadratic method, central limit theorem}
}
Document
Fixed Partial Match Queries in Quadtrees
Abstract
Several recent papers in the literature have addressed the analysis of the cost P_{n,q} of partial match search for a given fixed query q - that has s out of K specified coordinates - in different multidimensional data structures. Indeed, detailed asymptotic estimates for the main term in the expected cost P_{n,q} = E {P_{n,q}} in standard and relaxed K-d trees are known (for any dimension K and any number s of specified coordinates), as well as stronger distributional results on P_{n,q} for standard 2-d trees and 2-dimensional quadtrees. In this work we derive a precise asymptotic estimate for the main order term of P_{n,q} in quadtrees, for any values of K and s, 0 < s < K, under the assumption that the limit of P_{n,q}/n^alpha when n -> infty exists, where alpha is the exponent of n in the expected cost of a random partial match query with s specified coordinates in a random K-dimensional quadtree.
Cite as
Amalia Duch, Gustavo Lau, and Conrado Martínez. Fixed Partial Match Queries in Quadtrees. 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. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{duch_et_al:LIPIcs.AofA.2018.20,
author = {Duch, Amalia and Lau, Gustavo and Mart{\'\i}nez, Conrado},
title = {{Fixed Partial Match Queries in Quadtrees}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {20:1--20:18},
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.20},
URN = {urn:nbn:de:0030-drops-89136},
doi = {10.4230/LIPIcs.AofA.2018.20},
annote = {Keywords: Quadtree, Partial match queries, Associative queries, Multidimensional search, Analysis of algorithms}
}
Document
On the Tails of the Limiting QuickSort Density
Abstract
We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar upper bounds on absolute values of derivatives of f of each order.
Cite as
James Allen Fill and Wei-Chun Hung. On the Tails of the Limiting QuickSort Density. 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. 21:1-21:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fill_et_al:LIPIcs.AofA.2018.21,
author = {Fill, James Allen and Hung, Wei-Chun},
title = {{On the Tails of the Limiting QuickSort Density}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {21:1--21:10},
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.21},
URN = {urn:nbn:de:0030-drops-89144},
doi = {10.4230/LIPIcs.AofA.2018.21},
annote = {Keywords: Quicksort, density tails, asymptotic bounds, Landau-Kolmogorov inequality}
}
Document
Stationary Distribution Analysis of a Queueing Model with Local Choice
Abstract
The paper deals with load balancing between one-server queues on a circle by a local choice policy. Each one-server queue has a Poissonian arrival of customers. When a customer arrives at a queue, he joins the least loaded queue between this queue and the next one, ties solved at random. Service times have exponential distribution. The system is stable if the arrival-to-service rate ratio called load is less than one. When the load tends to zero, we derive the first terms of the expansion in this parameter for the stationary probabilities that a queue has 0 to 3 customers. We investigate the error, comparing these expansion results to numerical values obtained by simulations. Then we provide the asymptotics, as the load tends to zero, for the stationary probabilities of the queue length, for a fixed number of queues. It quantifies the difference between policies with this local choice, no choice and the choice between two queues chosen at random.
Cite as
Plinio S. Dester, Christine Fricker, and Hanene Mohamed. Stationary Distribution Analysis of a Queueing Model with Local Choice. 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. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dester_et_al:LIPIcs.AofA.2018.22,
author = {Dester, Plinio S. and Fricker, Christine and Mohamed, Hanene},
title = {{Stationary Distribution Analysis of a Queueing Model with Local Choice}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {22:1--22:18},
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.22},
URN = {urn:nbn:de:0030-drops-89152},
doi = {10.4230/LIPIcs.AofA.2018.22},
annote = {Keywords: queueing model, local choice, stationary analysis, balance equations, power series expansion}
}
Document
Refined Asymptotics for the Number of Leaves of Random Point Quadtrees
Abstract
In the early 2000s, several phase change results from distributional convergence to distributional non-convergence have been obtained for shape parameters of random discrete structures. Recently, for those random structures which admit a natural martingale process, these results have been considerably improved by obtaining refined asymptotics for the limit behavior. In this work, we propose a new approach which is also applicable to random discrete structures which do not admit a natural martingale process. As an example, we obtain refined asymptotics for the number of leaves in random point quadtrees. More applications, for example to shape parameters in generalized m-ary search trees and random gridtrees, will be discussed in the journal version of this extended abstract.
Cite as
Michael Fuchs, Noela S. Müller, and Henning Sulzbach. Refined Asymptotics for the Number of Leaves of Random Point Quadtrees. 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. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fuchs_et_al:LIPIcs.AofA.2018.23,
author = {Fuchs, Michael and M\"{u}ller, Noela S. and Sulzbach, Henning},
title = {{Refined Asymptotics for the Number of Leaves of Random Point Quadtrees}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {23:1--23:16},
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.23},
URN = {urn:nbn:de:0030-drops-89165},
doi = {10.4230/LIPIcs.AofA.2018.23},
annote = {Keywords: Quadtree, number of leaves, phase change, stochastic fixed-point equation, central limit theorem, positivity of variance, contraction method}
}
Document
Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices
Abstract
Many physical models undergo phase transitions as some parameter of the system is varied. This phenomenon has bearing on the convergence times for local Markov chains walking among the configurations of the physical system. One of the most basic examples of this phenomenon is the ferromagnetic Ising model on an n x n square lattice region Lambda with mixed boundary conditions. For this spin system, if we fix the spins on the top and bottom sides of the square to be + and the left and right sides to be -, a standard Peierls argument based on energy shows that below some critical temperature t_c, any local Markov chain M requires time exponential in n to mix.
Spin glasses are magnetic alloys that generalize the Ising model by specifying the strength of nearest neighbor interactions on the lattice, including whether they are ferromagnetic or antiferromagnetic. Whenever a face of the lattice is bounded by an odd number of edges with ferromagnetic interactions, the face is considered frustrated because the local competing objectives cannot be simultaneously satisfied. We consider spin glasses with exactly four well-separated frustrated faces that are symmetric around the center of the lattice region under 90 degree rotations. We show that local Markov chains require exponential time for all spin glasses in this class. This class includes the ferromagnetic Ising model with mixed boundary conditions described above, where the frustrated faces are on the boundary. The standard Peierls argument breaks down when the frustrated faces are on the interior of Lambda and yields weaker results when they are on the boundary of Lambda but not near the corners. We show that there is a universal temperature T below which M will be slow for all spin glasses with four well-separated frustrated faces. Our argument shows that there is an exponentially small cut indicated by the free energy, carefully exploiting both entropy and energy to establish a small bottleneck in the state space to establish slow mixing.
Cite as
David Gillman and Dana Randall. Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices. 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. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{gillman_et_al:LIPIcs.AofA.2018.24,
author = {Gillman, David and Randall, Dana},
title = {{Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {24:1--24:17},
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.24},
URN = {urn:nbn:de:0030-drops-89170},
doi = {10.4230/LIPIcs.AofA.2018.24},
annote = {Keywords: Mixing time, spin glass, Ising model, mixed boundary conditions, frustration}
}
Document
On the Number of Variables in Special Classes of Random Lambda-Terms
Abstract
We investigate the number of variables in two special subclasses of lambda-terms that are restricted by a bound of the number of abstractions between a variable and its binding lambda, and by a bound of the nesting levels of abstractions, respectively. These restrictions are on the one hand very natural from a practical point of view, and on the other hand they simplify the counting problem compared to that of unrestricted lambda-terms in such a way that the common methods of analytic combinatorics are applicable.
We will show that the total number of variables is asymptotically normally distributed for both subclasses of lambda-terms with mean and variance asymptotically equal to C_1 n and C_2 n, respectively, where the constants C_1 and C_2 depend on the bound that has been imposed. So far we just derived closed formulas for the constants in case of the class of lambda-terms with a bounded number of abstractions between each variable and its binding lambda. However, for the other class of lambda-terms that we consider, namely lambda-terms with a bounded number of nesting levels of abstractions, we investigate the number of variables in the different abstraction levels and thereby exhibit very interesting results concerning the distribution of the variables within those lambda-terms.
Cite as
Bernhard Gittenberger and Isabella Larcher. On the Number of Variables in Special Classes of Random Lambda-Terms. 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. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{gittenberger_et_al:LIPIcs.AofA.2018.25,
author = {Gittenberger, Bernhard and Larcher, Isabella},
title = {{On the Number of Variables in Special Classes of Random Lambda-Terms}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {25:1--25: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.25},
URN = {urn:nbn:de:0030-drops-89180},
doi = {10.4230/LIPIcs.AofA.2018.25},
annote = {Keywords: lambda-terms, directed acyclic graphs, singularity analysis, limiting distributions}
}
Document
Counting Ascents in Generalized Dyck Paths
Abstract
Non-negative Lukasiewicz paths are special two-dimensional lattice paths never passing below their starting altitude which have only one single special type of down step. They are well-known and -studied combinatorial objects, in particular due to their bijective relation to trees with given node degrees.
We study the asymptotic behavior of the number of ascents (i.e., the number of maximal sequences of consecutive up steps) of given length for classical subfamilies of general non-negative Lukasiewicz paths: those with arbitrary ending altitude, those ending on their starting altitude, and a variation thereof. Our results include precise asymptotic expansions for the expected number of such ascents as well as for the corresponding variance.
Cite as
Benjamin Hackl, Clemens Heuberger, and Helmut Prodinger. Counting Ascents in Generalized Dyck Paths. 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. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{hackl_et_al:LIPIcs.AofA.2018.26,
author = {Hackl, Benjamin and Heuberger, Clemens and Prodinger, Helmut},
title = {{Counting Ascents in Generalized Dyck Paths}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {26:1--26: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.26},
URN = {urn:nbn:de:0030-drops-89191},
doi = {10.4230/LIPIcs.AofA.2018.26},
annote = {Keywords: Lattice path, Lukasiewicz path, ascent, asymptotic analysis, implicit function, singular inversion}
}
Document
Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus
Abstract
The summatory function of a q-regular sequence in the sense of Allouche and Shallit is analysed asymptotically. The result is a sum of periodic fluctuations multiplied by a scaling factor. Each summand corresponds to an eigenvalues of absolute value larger than the joint spectral radius of the matrices of a linear representation of the sequence. The Fourier coefficients of the fluctuations are expressed in terms of residues of the corresponding Dirichlet generating function. A known pseudo Tauberian argument is extended in order to overcome convergence problems in Mellin-Perron summation.
Two examples are discussed in more detail: The case of sequences defined as the sum of outputs written by a transducer when reading a q-ary expansion of the input and the number of odd entries in the rows of Pascal's rhombus.
Cite as
Clemens Heuberger, Daniel Krenn, and Helmut Prodinger. Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus. 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. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{heuberger_et_al:LIPIcs.AofA.2018.27,
author = {Heuberger, Clemens and Krenn, Daniel and Prodinger, Helmut},
title = {{Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {27:1--27:18},
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.27},
URN = {urn:nbn:de:0030-drops-89204},
doi = {10.4230/LIPIcs.AofA.2018.27},
annote = {Keywords: Regular sequence, Mellin-Perron summation, summatory function, transducer, Pascal's rhombus}
}
Document
Distribution of the Number of Corners in Tree-like and Permutation Tableaux
Abstract
In this abstract, we study tree-like tableaux and some of their probabilistic properties. Tree-like tableaux are in bijection with other combinatorial structures, including permutation tableaux, and have a connection to the partially asymmetric simple exclusion process (PASEP), an important model of interacting particles system. In particular, in the context of tree-like tableaux, a corner corresponds to a node occupied by a particle that could jump to the right while inner corners indicate a particle with an empty node to its left. Thus, the total number of corners represents the number of nodes at which PASEP can move, i.e., the total current activity of the system. As the number of inner corners and regular corners is connected, we limit our discussion to just regular corners and show that, asymptotically, the number of corners in a tableaux of length n is normally distributed. Furthermore, since the number of corners in tree-like tableaux are closely related to the number of corners in permutation tableaux, we will discuss the corners in the context of the latter tableaux.
Cite as
Pawel Hitczenko and Aleksandr Yaroslavskiy. Distribution of the Number of Corners in Tree-like and Permutation 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. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{hitczenko_et_al:LIPIcs.AofA.2018.28,
author = {Hitczenko, Pawel and Yaroslavskiy, Aleksandr},
title = {{Distribution of the Number of Corners in Tree-like and Permutation Tableaux}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {28:1--28: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.28},
URN = {urn:nbn:de:0030-drops-89219},
doi = {10.4230/LIPIcs.AofA.2018.28},
annote = {Keywords: Tree-like tableaux, permutation tableaux, partially asymmetric simple exclusion process}
}
Document
Asymptotic Expansions for Sub-Critical Lagrangean Forms
Abstract
Asymptotic expansions for the Taylor coefficients of the Lagrangean form phi(z)=zf(phi(z)) are examined with a focus on the calculations of the asymptotic coefficients. The expansions are simple and useful, and we discuss their use in some enumerating sequences in trees, lattice paths and planar maps.
Cite as
Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh. Asymptotic Expansions for Sub-Critical Lagrangean Forms. 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. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{hwang_et_al:LIPIcs.AofA.2018.29,
author = {Hwang, Hsien-Kuei and Kang, Mihyun and Duh, Guan-Huei},
title = {{Asymptotic Expansions for Sub-Critical Lagrangean Forms}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {29:1--29: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.29},
URN = {urn:nbn:de:0030-drops-89224},
doi = {10.4230/LIPIcs.AofA.2018.29},
annote = {Keywords: asymptotic expansions, Lagrangean forms, saddle-point method, singularity analysis, maps}
}
Document
Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes
Abstract
Let f be a uniformly random element of the set of all mappings from [n] = {1, ..., n} to itself. Let T(f) and B(f) denote, respectively, the least common multiple and the product of the lengths of the cycles of f. Harris proved in 1973 that log T converges in distribution to a standard normal distribution and, in 2011, Schmutz obtained an asymptotic estimate on the logarithm of the expectation of T and B over all mappings on n nodes. We obtain analogous results for uniform random mappings on n = kr nodes with preimage sizes restricted to a set of the form {0,k}, where k = k(r) >= 2. This is motivated by the use of these classes of mappings as heuristic models for the statistics of polynomials of the form x^k + a over the integers modulo p, where k divides p - 1. We exhibit and discuss our numerical results on this heuristic.
Cite as
Rodrigo S. V. Martins, Daniel Panario, Claudio Qureshi, and Eric Schmutz. Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes. 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. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{martins_et_al:LIPIcs.AofA.2018.30,
author = {Martins, Rodrigo S. V. and Panario, Daniel and Qureshi, Claudio and Schmutz, Eric},
title = {{Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {30:1--30:11},
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.30},
URN = {urn:nbn:de:0030-drops-89237},
doi = {10.4230/LIPIcs.AofA.2018.30},
annote = {Keywords: random mappings with indegree restrictions, Brent-Pollard heuristic, periods of mappings}
}
Document
Modularity of Erdös-Rényi Random Graphs
Abstract
For a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q^*(G) (where 0 <= q^*(G)<= 1) of the graph G is defined to be the maximum over all vertex partitions of the modularity value. Given the prominence of modularity in community detection, it is an important graph parameter to understand mathematically.
For the Erdös-Rényi random graph G_{n,p} with n vertices and edge-probability p, the likely modularity has three distinct phases. For np <= 1+o(1) the modularity is 1+o(1) with high probability (whp), and for np --> infty the modularity is o(1) whp. Between these regions the modularity is non-trivial: for constants 1 < c_0 <= c_1 there exists delta>0 such that when c_0 <= np <= c_1 we have delta<q^*(G)<1-delta whp. For this critical region, we show that whp q^*(G_{n,p}) has order (np)^{-1/2}, in accord with a conjecture by Reichardt and Bornholdt in 2006 (and disproving another conjecture from the physics literature).
Cite as
Colin McDiarmid and Fiona Skerman. Modularity of Erdös-Rényi Random Graphs. 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. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{mcdiarmid_et_al:LIPIcs.AofA.2018.31,
author = {McDiarmid, Colin and Skerman, Fiona},
title = {{Modularity of Erd\"{o}s-R\'{e}nyi Random Graphs}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {31:1--31: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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.31},
URN = {urn:nbn:de:0030-drops-89242},
doi = {10.4230/LIPIcs.AofA.2018.31},
annote = {Keywords: Community detection, Newman-Girvan Modularity, random graphs}
}
Document
Counting Planar Tanglegrams
Abstract
Tanglegrams are structures consisting of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the two trees. We say that a tanglegram is planar if it can be drawn in the plane without crossings. Using a blend of combinatorial and analytic techniques, we determine an asymptotic formula for the number of planar tanglegrams with n leaves on each side.
Cite as
Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, and Stephan Wagner. Counting Planar Tanglegrams. 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. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2018.32,
author = {Ralaivaosaona, Dimbinaina and Ravelomanana, Jean Bernoulli and Wagner, Stephan},
title = {{Counting Planar Tanglegrams}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {32:1--32:18},
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.32},
URN = {urn:nbn:de:0030-drops-89259},
doi = {10.4230/LIPIcs.AofA.2018.32},
annote = {Keywords: rooted binary trees, tanglegram, planar, generating functions, asymptotic enumeration, singularity analysis}
}
Document
Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees
Abstract
An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Janson recently proved a central limit theorem for additive functionals of conditioned Galton-Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are almost local, thus covering a wider range of functionals. Our main result is illustrated by two explicit examples: the (logarithm of) the number of matchings, and a functional stemming from a tree reduction process that was studied by Hackl, Heuberger, Kropf, and Prodinger.
Cite as
Dimbinaina Ralaivaosaona, Matas Sileikis, and Stephan Wagner. Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson 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. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2018.33,
author = {Ralaivaosaona, Dimbinaina and Sileikis, Matas and Wagner, Stephan},
title = {{Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {33:1--33:17},
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.33},
URN = {urn:nbn:de:0030-drops-89262},
doi = {10.4230/LIPIcs.AofA.2018.33},
annote = {Keywords: Galton-Watson trees, central limit theorem, additive functional}
}
Document
Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex
Abstract
We prove limit theorems describing the asymptotic behaviour of a typical vertex in random simply generated trees as their sizes tends to infinity. In the standard case of a critical Galton-Watson tree conditioned to be large, the limit is the invariant random sin-tree constructed by Aldous (1991). Our main contribution lies in the condensation regime where vertices of macroscopic degree appear. Here we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with "large" degree. Beyond this distinguished ancestor, different behaviours may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the important case where the offspring distribution follows a power law up to a factor that varies slowly at infinity.
Cite as
Benedikt Stufler. Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex. 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. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{stufler:LIPIcs.AofA.2018.34,
author = {Stufler, Benedikt},
title = {{Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {34:1--34:11},
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.34},
URN = {urn:nbn:de:0030-drops-89276},
doi = {10.4230/LIPIcs.AofA.2018.34},
annote = {Keywords: Galton-Watson trees, local weak limits}
}
Document
The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace
Abstract
This paper is devoted to the Depoissonisation process which is central in various analyses of the AofA domain. We first recall in Section 1 the two possible paths that may be used in this process, namely the Depoissonisation path and the Rice path. The two paths are rarely described for themselves in the literature, and general methodological results are often difficult to isolate amongst particular results that are more directed towards various applications. The main results for the Depoissonisation path are scattered in at least five papers, with a chronological order which does not correspond to the logical order of the method. The Rice path is also almost always presented with a strong focus towards possible applications. It is often very easy to apply, but it needs a tameness condition, which appears a priori to be quite restrictive, and is not deeply studied in the literature. This explains why the Rice path is very often undervalued.
Second, the two paths are not precisely compared, and the situation creates various "feelings": some people see the tools that are used in the two paths as quite different, and strongly prefer one of the two paths; some others think the two paths are almost the same, with just a change of vocabulary. It is thus useful to compare the two paths and the tools they use. This will be done in Sections 2 and 3. We also "follow" this comparison on a precise problem, related to the analysis of tries, introduced in Section 1.7.
The paper also exhibits in Section 4 a new framework, of practical use, where the tameness condition of Rice path is proven to hold. This approach, perhaps of independent interest, deals with the shifting of sequences and then the inverse Laplace transform, which does not seem of classical use in this context. It performs very simple computations. This adds a new method to the Depoissonisation context and explains the title of the paper. We then conclude that the Rice path is both of easy and practical use: even though (much?) less general than the Depoissonisation path, it is easier to apply.
Cite as
Brigitte Vallée. The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace. 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. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{vallee:LIPIcs.AofA.2018.35,
author = {Vall\'{e}e, Brigitte},
title = {{The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {35:1--35:20},
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.35},
URN = {urn:nbn:de:0030-drops-89284},
doi = {10.4230/LIPIcs.AofA.2018.35},
annote = {Keywords: Analysis of Algorithms, Poisson model, Mellin transform, Rice integral, Laplace transform, Newton interpolation, Depoissonisation, sources, trie structure, algorithms on words}
}
Document
Average Cost of QuickXsort with Pivot Sampling
Abstract
QuickXsort is a strategy to combine Quicksort with another sorting method X so that the result has essentially the same comparison cost as X in isolation, but sorts in place even when X requires a linear-size buffer. We solve the recurrence for QuickXsort precisely up to the linear term including the optimization to choose pivots from a sample of k elements. This allows to immediately obtain overall average costs using only the average costs of sorting method X (as if run in isolation). We thereby extend and greatly simplify the analysis of QuickHeapsort and QuickMergesort with practically efficient pivot selection, and give the first tight upper bounds including the linear term for such methods.
Cite as
Sebastian Wild. Average Cost of QuickXsort with Pivot Sampling. 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. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{wild:LIPIcs.AofA.2018.36,
author = {Wild, Sebastian},
title = {{Average Cost of QuickXsort with Pivot Sampling}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {36:1--36:19},
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.36},
URN = {urn:nbn:de:0030-drops-89295},
doi = {10.4230/LIPIcs.AofA.2018.36},
annote = {Keywords: in-situ sorting, constant-factor optimal sorting, pivot sampling, QuickMergesort, QuickHeapsort, Quicksort recurrence, average-case analysis}
}