Volume
LIPIcs, Volume 159
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Publication Details
- published at: 2020-06-10
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-147-4
- DBLP: db/conf/aofa/aofa2020
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 159, AofA 2020, Complete Volume
Abstract
LIPIcs, Volume 159, AofA 2020, Complete Volume
Cite as
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 1-402, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@Proceedings{drmota_et_al:LIPIcs.AofA.2020,
title = {{LIPIcs, Volume 159, AofA 2020, Complete Volume}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {1--402},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020},
URN = {urn:nbn:de:0030-drops-120296},
doi = {10.4230/LIPIcs.AofA.2020},
annote = {Keywords: LIPIcs, Volume 159, AofA 2020, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{drmota_et_al:LIPIcs.AofA.2020.0,
author = {Drmota, Michael and Heuberger, Clemens},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {0:i--0:xii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.0},
URN = {urn:nbn:de:0030-drops-120309},
doi = {10.4230/LIPIcs.AofA.2020.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution
Abstract
In this article, we analyse the joint distribution of some given set of patterns in fundamental combinatorial structures such as words and random walks (directed lattice paths on ℤ²). Our method relies on a vectorial generalization of the classical kernel method, and on a matricial generalization of the autocorrelation polynomial (thus extending the univariate case of Guibas and Odlyzko). This gives access to the multivariate generating functions, for walks, meanders (walks constrained to be above the x-axis), and excursions (meanders constrained to end on the x-axis). We then demonstrate the power of our methods by obtaining closed-form expressions for an infinite family of models, in terms of simple combinatorial quantities. Finally, we prove that the joint distribution of the patterns in walks/bridges/excursions/meanders satisfies a multivariate Gaussian limit law.
Cite as
Andrei Asinowski and Cyril Banderier. On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{asinowski_et_al:LIPIcs.AofA.2020.1,
author = {Asinowski, Andrei and Banderier, Cyril},
title = {{On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {1:1--1:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.1},
URN = {urn:nbn:de:0030-drops-120317},
doi = {10.4230/LIPIcs.AofA.2020.1},
annote = {Keywords: Lattice path, Dyck path, Motzkin path, generating function, algebraic function, kernel method, context-free grammar, multivariate Gaussian distribution}
}
Document
Latticepathology and Symmetric Functions (Extended Abstract)
Abstract
In this article, we revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener - Hopf formulas, thus capturing joint distributions. We also show that each of the fundamental families of symmetric polynomials corresponds to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Cite as
Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2,
author = {Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael},
title = {{Latticepathology and Symmetric Functions (Extended Abstract)}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {2:1--2:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2},
URN = {urn:nbn:de:0030-drops-120329},
doi = {10.4230/LIPIcs.AofA.2020.2},
annote = {Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization}
}
Document
The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings
Abstract
We describe a multiple string pattern matching algorithm which is well-suited for approximate search and dictionaries composed of words of different lengths. We prove that this algorithm has optimal complexity rate up to a multiplicative constant, for arbitrary dictionaries. This extends to arbitrary dictionaries the classical results of Yao [SIAM J. Comput. 8, 1979], and Chang and Marr [Proc. CPM94, 1994].
Cite as
Frédérique Bassino, Tsinjo Rakotoarimalala, and Andrea Sportiello. The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bassino_et_al:LIPIcs.AofA.2020.3,
author = {Bassino, Fr\'{e}d\'{e}rique and Rakotoarimalala, Tsinjo and Sportiello, Andrea},
title = {{The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.3},
URN = {urn:nbn:de:0030-drops-120336},
doi = {10.4230/LIPIcs.AofA.2020.3},
annote = {Keywords: Average-case analysis of algorithms, String Pattern Matching, Computational Complexity bounds}
}
Document
Two Arithmetical Sources and Their Associated Tries
Abstract
This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth.
The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.
Cite as
Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée. Two Arithmetical Sources and Their Associated Tries. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{berthe_et_al:LIPIcs.AofA.2020.4,
author = {Berth\'{e}, Val\'{e}rie and Cesaratto, Eda and Paccaut, Fr\'{e}d\'{e}ric and Rotondo, Pablo and Safe, Mart{\'\i}n D. and Vall\'{e}e, Brigitte},
title = {{Two Arithmetical Sources and Their Associated Tries}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {4:1--4:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.4},
URN = {urn:nbn:de:0030-drops-120345},
doi = {10.4230/LIPIcs.AofA.2020.4},
annote = {Keywords: Combinatorics of words, Information Theory, Probabilistic analysis, Analytic combinatorics, Dirichlet generating functions, Sources, Partitions, Trie structure, Continued fraction expansion, Farey map, Sturm words, Transfer operator}
}
Document
The k-Cut Model in Conditioned Galton-Watson Trees
Abstract
The k-cut number of rooted graphs was introduced by Cai et al. [Cai and Holmgren, 2019] as a generalization of the classical cutting model by Meir and Moon [Meir and Moon, 1970]. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson [Janson, 2006].
Cite as
Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren. The k-Cut Model in Conditioned Galton-Watson Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.5,
author = {Berzunza, Gabriel and Cai, Xing Shi and Holmgren, Cecilia},
title = {{The k-Cut Model in Conditioned Galton-Watson Trees}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {5:1--5:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.5},
URN = {urn:nbn:de:0030-drops-120352},
doi = {10.4230/LIPIcs.AofA.2020.5},
annote = {Keywords: k-cut, cutting, conditioned Galton-Watson trees}
}
Document
Largest Clusters for Supercritical Percolation on Split Trees
Abstract
We consider the model of random trees introduced by Devroye [Devroye, 1999], the so-called random split trees. The model encompasses many important randomized algorithms and data structures. We then perform supercritical Bernoulli bond-percolation on those trees and obtain a precise weak limit theorem for the sizes of the largest clusters. The approach we develop may be useful for studying percolation on other classes of trees with logarithmic height, for instance, we have also studied the case of complete d-regular trees.
Cite as
Gabriel Berzunza and Cecilia Holmgren. Largest Clusters for Supercritical Percolation on Split Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.6,
author = {Berzunza, Gabriel and Holmgren, Cecilia},
title = {{Largest Clusters for Supercritical Percolation on Split Trees}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {6:1--6:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.6},
URN = {urn:nbn:de:0030-drops-120361},
doi = {10.4230/LIPIcs.AofA.2020.6},
annote = {Keywords: Split trees, random trees, supercritical bond-percolation, cluster size, Poisson measures}
}
Document
Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes
Abstract
Baxter permutations, plane bipolar orientations, and a specific family of walks in the non-negative quadrant are well-known to be related to each other through several bijections. We introduce a further new family of discrete objects, called coalescent-walk processes, that are fundamental for our results. We relate these new objects with the other previously mentioned families introducing some new bijections.
We prove joint Benjamini - Schramm convergence (both in the annealed and quenched sense) for uniform objects in the four families. Furthermore, we explicitly construct a new fractal random measure of the unit square, called the coalescent Baxter permuton and we show that it is the scaling limit (in the permuton sense) of uniform Baxter permutations.
To prove the latter result, we study the scaling limit of the associated random coalescent-walk processes. We show that they converge in law to a continuous random coalescent-walk process encoded by a perturbed version of the Tanaka stochastic differential equation. This result has connections (to be explored in future projects) with the results of Gwynne, Holden, Sun (2016) on scaling limits (in the Peanosphere topology) of plane bipolar triangulations.
We further prove some results that relate the limiting objects of the four families to each other, both in the local and scaling limit case.
Cite as
Jacopo Borga and Mickaël Maazoun. Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{borga_et_al:LIPIcs.AofA.2020.7,
author = {Borga, Jacopo and Maazoun, Micka\"{e}l},
title = {{Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {7:1--7:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.7},
URN = {urn:nbn:de:0030-drops-120370},
doi = {10.4230/LIPIcs.AofA.2020.7},
annote = {Keywords: Local and scaling limits, permutations, planar maps, random walks in cones}
}
Document
More Models of Walks Avoiding a Quadrant
Abstract
We continue the enumeration of plane lattice paths avoiding the negative quadrant initiated by the first author in [Bousquet-Mélou, 2016]. We solve in detail a new case, the king walks, where all 8 nearest neighbour steps are allowed. As in the two cases solved in [Bousquet-Mélou, 2016], the associated generating function is proved to differ from a simple, explicit D-finite series (related to the enumeration of walks confined to the first quadrant) by an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou, 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree.
We also explain why we expect the observed algebraicity phenomenon to persist for 4 more models, for which the quadrant problem is solvable using the reflection principle.
Cite as
Mireille Bousquet-Mélou and Michael Wallner. More Models of Walks Avoiding a Quadrant. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bousquetmelou_et_al:LIPIcs.AofA.2020.8,
author = {Bousquet-M\'{e}lou, Mireille and Wallner, Michael},
title = {{More Models of Walks Avoiding a Quadrant}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.8},
URN = {urn:nbn:de:0030-drops-120383},
doi = {10.4230/LIPIcs.AofA.2020.8},
annote = {Keywords: Enumerative combinatorics, lattice paths, non-convex cones, algebraic series, D-finite series}
}
Document
Polyharmonic Functions And Random Processes in Cones
Abstract
We investigate polyharmonic functions associated to Brownian motions and random walks in cones. These are functions which cancel some power of the usual Laplacian in the continuous setting and of the discrete Laplacian in the discrete setting. We show that polyharmonic functions naturally appear while considering asymptotic expansions of the heat kernel in the Brownian case and in lattice walk enumeration problems. We provide a method to construct general polyharmonic functions through Laplace transforms and generating functions in the continuous and discrete cases, respectively. This is done by using a functional equation approach.
Cite as
François Chapon, Éric Fusy, and Kilian Raschel. Polyharmonic Functions And Random Processes in Cones. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{chapon_et_al:LIPIcs.AofA.2020.9,
author = {Chapon, Fran\c{c}ois and Fusy, \'{E}ric and Raschel, Kilian},
title = {{Polyharmonic Functions And Random Processes in Cones}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {9:1--9:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.9},
URN = {urn:nbn:de:0030-drops-120390},
doi = {10.4230/LIPIcs.AofA.2020.9},
annote = {Keywords: Brownian motion in cones, Heat kernel, Random walks in cones, Harmonic functions, Polyharmonic functions, Complete asymptotic expansions, Functional equations}
}
Document
Cut Vertices in Random Planar Maps
Abstract
The main goal of this paper is to determine the asymptotic behavior of the number X_n of cut-vertices in random planar maps with n edges. It is shown that X_n/n → c in probability (for some explicit c>0). For so-called subcritial subclasses of planar maps like outerplanar maps we obtain a central limit theorem, too.
Cite as
Michael Drmota, Marc Noy, and Benedikt Stufler. Cut Vertices in Random Planar Maps. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{drmota_et_al:LIPIcs.AofA.2020.10,
author = {Drmota, Michael and Noy, Marc and Stufler, Benedikt},
title = {{Cut Vertices in Random Planar Maps}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {10:1--10:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.10},
URN = {urn:nbn:de:0030-drops-120403},
doi = {10.4230/LIPIcs.AofA.2020.10},
annote = {Keywords: random planar maps, cut vertices, generating functions, local graph limits}
}
Document
Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language
Abstract
We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.
Cite as
Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{elveyprice_et_al:LIPIcs.AofA.2020.11,
author = {Elvey Price, Andrew and Fang, Wenjie and Wallner, Michael},
title = {{Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {11:1--11:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.11},
URN = {urn:nbn:de:0030-drops-120419},
doi = {10.4230/LIPIcs.AofA.2020.11},
annote = {Keywords: Airy function, asymptotics, directed acyclic graphs, Dyck paths, bijection, stretched exponential, compacted trees, minimal automata, finite languages}
}
Document
The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem
Abstract
Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, but a bijective proof for any of these equivalences has been elusive for almost 40 years. In this extended abstract, we provide a sketch of the first bijective proof of the enumeration formula for alternating sign matrices, and of the fact that alternating sign matrices are equinumerous with descending plane partitions. The bijections are based on the operator formula for the number of monotone triangles due to the first author. The starting point for these constructions were known "computational" proofs, but the combinatorial point of view led to several drastic modifications and simplifications. We also provide computer code where all of our constructions have been implemented.
Cite as
Ilse Fischer and Matjaž Konvalinka. The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{fischer_et_al:LIPIcs.AofA.2020.12,
author = {Fischer, Ilse and Konvalinka, Matja\v{z}},
title = {{The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {12:1--12:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.12},
URN = {urn:nbn:de:0030-drops-120424},
doi = {10.4230/LIPIcs.AofA.2020.12},
annote = {Keywords: enumeration, bijective proof, alternating sign matrix, plane partition}
}
Document
Counting Cubic Maps with Large Genus
Abstract
We derive an asymptotic expression for the number of cubic maps on orientable surfaces when the genus is proportional to the number of vertices. Let Σ_g denote the orientable surface of genus g and θ=g/n∈ (0,1/2). Given g,n∈ ℕ with g→ ∞ and n/2-g→ ∞ as n→ ∞, the number C_{n,g} of cubic maps on Σ_g with 2n vertices satisfies C_{n,g} ∼ (g!)² α(θ) β(θ)ⁿ γ(θ)^{2g}, as g→ ∞, where α(θ),β(θ),γ(θ) are differentiable functions in (0,1/2). This also leads to the asymptotic number of triangulations (as the dual of cubic maps) with large genus. When g/n lies in a closed subinterval of (0,1/2), the asymptotic formula can be obtained using a local limit theorem. The saddle-point method is applied when g/n→ 0 or g/n→ 1/2.
Cite as
Zhicheng Gao and Mihyun Kang. Counting Cubic Maps with Large Genus. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{gao_et_al:LIPIcs.AofA.2020.13,
author = {Gao, Zhicheng and Kang, Mihyun},
title = {{Counting Cubic Maps with Large Genus}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {13:1--13:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.13},
URN = {urn:nbn:de:0030-drops-120437},
doi = {10.4230/LIPIcs.AofA.2020.13},
annote = {Keywords: cubic maps, triangulations, cubic graphs on surfaces, generating functions, asymptotic enumeration, local limit theorem, saddle-point method}
}
Document
Diffusion Limits in the Online Subsequence Selection Problems
Abstract
In the stochastic sequential optimisation problems it is of interest to study features of strategies more delicate than just their performance measure. In this talk we focus on variations of the online monotone subsequence and bin packing problems, where it is possible to give a fairly explicit asymptotic description of the selection processes under strategies that are sufficiently close to optimality. We show that the transversal fluctuations of the shape and the length of selected subsequence approach Gaussian functional limits that are very different from their counterparts in the offline problem, where the full set of data can be used in selection algorithms.
Cite as
Alexander Gnedin and Amirlan Seksenbayev. Diffusion Limits in the Online Subsequence Selection Problems. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{gnedin_et_al:LIPIcs.AofA.2020.14,
author = {Gnedin, Alexander and Seksenbayev, Amirlan},
title = {{Diffusion Limits in the Online Subsequence Selection Problems}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.14},
URN = {urn:nbn:de:0030-drops-120444},
doi = {10.4230/LIPIcs.AofA.2020.14},
annote = {Keywords: sequential optimisation, longest increasing subsequence, bin packing, fluctuations in the selection process, functional limit}
}
Document
Analysis of Lempel-Ziv'78 for Markov Sources
Abstract
Lempel-Ziv'78 is one of the most popular data compression algorithms. Over the last few decades fascinating properties of LZ78 were uncovered. Among others, in 1995 we settled the Ziv conjecture by proving that for a memoryless source the number of LZ78 phrases satisfies the Central Limit Theorem (CLT). Since then the quest commenced to extend it to Markov sources. However, despite several attempts this problem is still open. The 1995 proof of the Ziv conjecture was based on two models: In the DST-model, the associated digital search tree (DST) is built over m independent strings. In the LZ-model a single string of length n is partitioned into variable length phrases such that the next phrase is not seen in the past as a phrase. The Ziv conjecture for memoryless source was settled by proving that both DST-model and the LZ-model are asymptotically equivalent. The main result of this paper shows that this is not the case for the LZ78 algorithm over Markov sources. In addition, we develop here a large deviation for the number of phrases in the LZ78 and give a precise asymptotic expression for the redundancy which is the excess of LZ78 code over the entropy of the source. We establish these findings using a combination of combinatorial and analytic tools. In particular, to handle the strong dependency between Markov phrases, we introduce and precisely analyze the so called tail symbol which is the first symbol of the next phrase in the LZ78 parsing.
Cite as
Philippe Jacquet and Wojciech Szpankowski. Analysis of Lempel-Ziv'78 for Markov Sources. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{jacquet_et_al:LIPIcs.AofA.2020.15,
author = {Jacquet, Philippe and Szpankowski, Wojciech},
title = {{Analysis of Lempel-Ziv'78 for Markov Sources}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {15:1--15:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.15},
URN = {urn:nbn:de:0030-drops-120459},
doi = {10.4230/LIPIcs.AofA.2020.15},
annote = {Keywords: Lempel-Ziv algorithm, digital search trees, depoissonization, analytic combinatorics, large deviations}
}
Document
Power-Law Degree Distribution in the Connected Component of a Duplication Graph
Abstract
We study the partial duplication dynamic graph model, introduced by Bhan et al. in [Bhan et al., 2002] in which a newly arrived node selects randomly an existing node and connects with probability p to its neighbors. Such a dynamic network is widely considered to be a good model for various biological networks such as protein-protein interaction networks. This model is discussed in numerous publications with only a few recent rigorous results, especially for the degree distribution. Recently Jordan [Jordan, 2018] proved that for 0 < p < 1/e the degree distribution of the connected component is stationary with approximately a power law. In this paper we rigorously prove that the tail is indeed a true power law, that is, we show that the degree of a randomly selected node in the connected component decays like C/k^β where C an explicit constant and β ≠ 2 is a non-trivial solution of p^(β-2) + β - 3 = 0. This holds regardless of the structure of the initial graph, as long as it is connected and has at least two vertices. To establish this finding we apply analytic combinatorics tools, in particular Mellin transform and singularity analysis.
Cite as
Philippe Jacquet, Krzysztof Turowski, and Wojciech Szpankowski. Power-Law Degree Distribution in the Connected Component of a Duplication Graph. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{jacquet_et_al:LIPIcs.AofA.2020.16,
author = {Jacquet, Philippe and Turowski, Krzysztof and Szpankowski, Wojciech},
title = {{Power-Law Degree Distribution in the Connected Component of a Duplication Graph}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {16:1--16:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.16},
URN = {urn:nbn:de:0030-drops-120467},
doi = {10.4230/LIPIcs.AofA.2020.16},
annote = {Keywords: random graphs, pure duplication model, degree distribution, tail exponent, analytic combinatorics}
}
Document
Hidden Words Statistics for Large Patterns
Abstract
We study here the so called subsequence pattern matching also known as hidden pattern matching in which one searches for a given pattern w of length m as a subsequence in a random text of length n. The quantity of interest is the number of occurrences of w as a subsequence (i.e., occurring in not necessarily consecutive text locations). This problem finds many applications from intrusion detection, to trace reconstruction, to deletion channel, and to DNA-based storage systems. In all of these applications, the pattern w is of variable length. To the best of our knowledge this problem was only tackled for a fixed length m=O(1) [P. Flajolet et al., 2006]. In our main result Theorem 5 we prove that for m=o(n^{1/3}) the number of subsequence occurrences is normally distributed. In addition, in Theorem 6 we show that under some constraints on the structure of w the asymptotic normality can be extended to m=o(√n). For a special pattern w consisting of the same symbol, we indicate that for m=o(n) the distribution of number of subsequences is either asymptotically normal or asymptotically log normal. We conjecture that this dichotomy is true for all patterns. We use Hoeffding’s projection method for U-statistics to prove our findings.
Cite as
Svante Janson and Wojciech Szpankowski. Hidden Words Statistics for Large Patterns. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{janson_et_al:LIPIcs.AofA.2020.17,
author = {Janson, Svante and Szpankowski, Wojciech},
title = {{Hidden Words Statistics for Large Patterns}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {17:1--17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.17},
URN = {urn:nbn:de:0030-drops-120476},
doi = {10.4230/LIPIcs.AofA.2020.17},
annote = {Keywords: Hidden pattern matching, subsequences, probability, U-statistics, projection method}
}
Document
The Giant Component and 2-Core in Sparse Random Outerplanar Graphs
Abstract
Let A(n,m) be a graph chosen uniformly at random from the class of all vertex-labelled outerplanar graphs with n vertices and m edges. We consider A(n,m) in the sparse regime when m=n/2+s for s=o(n). We show that with high probability the giant component in A(n,m) emerges at m=n/2+O (n^{2/3}) and determine the typical order of the 2-core. In addition, we prove that if s=ω(n^{2/3}), with high probability every edge in A(n,m) belongs to at most one cycle.
Cite as
Mihyun Kang and Michael Missethan. The Giant Component and 2-Core in Sparse Random Outerplanar Graphs. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kang_et_al:LIPIcs.AofA.2020.18,
author = {Kang, Mihyun and Missethan, Michael},
title = {{The Giant Component and 2-Core in Sparse Random Outerplanar Graphs}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.18},
URN = {urn:nbn:de:0030-drops-120488},
doi = {10.4230/LIPIcs.AofA.2020.18},
annote = {Keywords: giant component, core, outerplanar graphs, singularity analysis}
}
Document
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics
Abstract
Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms.
The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős - Rényi random graphs) have been used so far.
In this paper we extend these findings to sparse graphs, with a focus on grid graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a grid graph, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio.
Cite as
Stefan Klootwijk and Bodo Manthey. Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{klootwijk_et_al:LIPIcs.AofA.2020.19,
author = {Klootwijk, Stefan and Manthey, Bodo},
title = {{Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {19:1--19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.19},
URN = {urn:nbn:de:0030-drops-120494},
doi = {10.4230/LIPIcs.AofA.2020.19},
annote = {Keywords: Random shortest paths, Random metrics, Approximation algorithms, First-passage percolation}
}
Document
Greedy Maximal Independent Sets via Local Limits
Abstract
The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science - and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge.
In this paper we present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to study new ones, such as random trees.
We conclude our work by analysing the random greedy algorithm more closely when the base graph is a tree. We show that in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order.
Cite as
Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman. Greedy Maximal Independent Sets via Local Limits. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{krivelevich_et_al:LIPIcs.AofA.2020.20,
author = {Krivelevich, Michael and M\'{e}sz\'{a}ros, Tam\'{a}s and Michaeli, Peleg and Shikhelman, Clara},
title = {{Greedy Maximal Independent Sets via Local Limits}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {20:1--20:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.20},
URN = {urn:nbn:de:0030-drops-120507},
doi = {10.4230/LIPIcs.AofA.2020.20},
annote = {Keywords: Greedy maximal independent set, random graph, local limit}
}
Document
The Disordered Chinese Restaurant and Other Competing Growth Processes
Abstract
The disordered Chinese restaurant process is a partition-valued stochastic process where the elements of the partitioned set are seen as customers sitting at different tables (the sets of the partition) in a restaurant. Each table is assigned a positive number called its attractiveness. At every step a customer enters the restaurant and either joins a table with a probability proportional to the product of its attractiveness and the number of customers sitting at the table, or occupies a previously unoccupied table, which is then assigned an attractiveness drawn from a bounded distribution independently of everything else. When all attractivenesses are equal to the upper bound this process is the classical Chinese restaurant process; we show that the introduction of disorder can drastically change the behaviour of the system. Our main results are distributional limit theorems for the scaled number of customers at the busiest table, and for the ratio of occupants at the busiest and second busiest table. The limiting distributions are universal, i.e. they do not depend on the distribution of the attractiveness. They follow from two general Poisson limit theorems for a broad class of processes consisting of families growing with different rates from different birth times, which have further applications, for example to preferential attachment networks.
Cite as
Cécile Mailler, Peter Mörters, and Anna Senkevich. The Disordered Chinese Restaurant and Other Competing Growth Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{mailler_et_al:LIPIcs.AofA.2020.21,
author = {Mailler, C\'{e}cile and M\"{o}rters, Peter and Senkevich, Anna},
title = {{The Disordered Chinese Restaurant and Other Competing Growth Processes}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.21},
URN = {urn:nbn:de:0030-drops-120511},
doi = {10.4230/LIPIcs.AofA.2020.21},
annote = {Keywords: Chinese restaurant process, competing growth processes, reinforced branching processes, preferential attachment tree with fitness, Poisson processes}
}
Document
Convergence Rates in the Probabilistic Analysis of Algorithms
Abstract
In this extended abstract a general framework is developed to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. Concrete examples from the analysis of algorithms and data structures are discussed as well as a few examples from other areas. They lead to convergence rates of polynomial and logarithmic order. Our results show how to obtain a significantly better bound for the rate of convergence when the limiting distribution is Gaussian.
Cite as
Ralph Neininger and Jasmin Straub. Convergence Rates in the Probabilistic Analysis of Algorithms. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{neininger_et_al:LIPIcs.AofA.2020.22,
author = {Neininger, Ralph and Straub, Jasmin},
title = {{Convergence Rates in the Probabilistic Analysis of Algorithms}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {22:1--22:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.22},
URN = {urn:nbn:de:0030-drops-120529},
doi = {10.4230/LIPIcs.AofA.2020.22},
annote = {Keywords: weak convergence, probabilistic analysis of algorithms, random trees, probability metrics}
}
Document
Hidden Independence in Unstructured Probabilistic Models
Abstract
We describe a novel way to represent the probability distribution of a random binary string as a mixture having a maximally weighted component associated with independent (though not necessarily identically distributed) Bernoulli characters. We refer to this as the latent independent weight of the probabilistic source producing the string, and derive a combinatorial algorithm to compute it. The decomposition we propose may serve as an alternative to the Boolean paradigm of hypothesis testing, or to assess the fraction of uncorrupted samples originating from a source with independent marginal distributions. In this sense, the latent independent weight quantifies the maximal amount of independence contained within a probabilistic source, which, properly speaking, may not have independent marginal distributions.
Cite as
Antony Pearson and Manuel E. Lladser. Hidden Independence in Unstructured Probabilistic Models. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{pearson_et_al:LIPIcs.AofA.2020.23,
author = {Pearson, Antony and Lladser, Manuel E.},
title = {{Hidden Independence in Unstructured Probabilistic Models}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {23:1--23:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.23},
URN = {urn:nbn:de:0030-drops-120538},
doi = {10.4230/LIPIcs.AofA.2020.23},
annote = {Keywords: Bayesian networks, contamination, latent weights, mixture models, independence, symbolic data}
}
Document
Block Statistics in Subcritical Graph Classes
Abstract
We study block statistics in subcritical graph classes; these are statistics that can be defined as the sum of a certain weight function over all blocks. Examples include the number of edges, the number of blocks, and the logarithm of the number of spanning trees. The main result of this paper is a central limit theorem for statistics of this kind under fairly mild technical assumptions.
Cite as
Dimbinaina Ralaivaosaona, Clément Requilé, and Stephan Wagner. Block Statistics in Subcritical Graph Classes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2020.24,
author = {Ralaivaosaona, Dimbinaina and Requil\'{e}, Cl\'{e}ment and Wagner, Stephan},
title = {{Block Statistics in Subcritical Graph Classes}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {24:1--24:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.24},
URN = {urn:nbn:de:0030-drops-120543},
doi = {10.4230/LIPIcs.AofA.2020.24},
annote = {Keywords: subcritical graph class, block statistic, number of blocks, number of edges, number of spanning trees}
}
Document
On the Probability That a Random Digraph Is Acyclic
Abstract
Given a positive integer n and a real number p ∈ [0,1], let D(n,p) denote the random digraph defined in the following way: each of the binom(n,2) possible edges on the vertex set {1,2,3,…,n} is included with probability 2p, where all edges are independent of each other. Thereafter, a direction is chosen independently for each edge, with probability 1/2 for each possible direction. In this paper, we study the probability that a random instance of D(n,p) is acyclic, i.e., that it does not contain a directed cycle. We find precise asymptotic formulas for the probability of a random digraph being acyclic in the sparse regime, i.e., when np = O(1). As an example, for each real number μ, we find an exact analytic expression for φ(μ) = lim_{n→ ∞} n^{1/3} ℙ{D(n,1/n (1+μ n^{-1/3})) is acyclic}.
Cite as
Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner. On the Probability That a Random Digraph Is Acyclic. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2020.25,
author = {Ralaivaosaona, Dimbinaina and Rasendrahasina, Vonjy and Wagner, Stephan},
title = {{On the Probability That a Random Digraph Is Acyclic}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {25:1--25:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Drmota, Michael and Heuberger, Clemens},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.25},
URN = {urn:nbn:de:0030-drops-120557},
doi = {10.4230/LIPIcs.AofA.2020.25},
annote = {Keywords: Random digraphs, acyclic digraphs, asymptotics}
}