LIPIcs.AofA.2020.24.pdf
- Filesize: 409 kB
- 14 pages
Document
Block Statistics in Subcritical Graph Classes
Authors
-
Part of:
Volume:
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-10
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.AofA.2020.24
https://doi.org/10.4230/LIPIcs.AofA.2020.24
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Random graphs
- Mathematics of computing → Generating functions
Keywords
- subcritical graph class
- block statistic
- number of blocks
- number of edges
- number of spanning trees
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Manuel Bodirsky, Omer Giménez, Mihyun Kang, and Marc Noy. Enumeration and limit laws for series-parallel graphs. European Journal of Combinatorics, 28(8):2091-2105, 2007.
-
Guillaume Chapuy, Éric Fusy, Mihyun Kang, and Bilyana Shoilekova. A complete grammar for decomposing a family of graphs into 3-connected components. The Electronic Journal of Combinatorics, 15(R148), 2008.
-
Michael Drmota. Random Trees. SpringerWienNewYork, Vienna, 2009.
-
Michael Drmota, Éric Fusy, Mihyun Kang, Veronika Kraus, and Juanjo Rué. Asymptotic study of subcritical graph classes. SIAM Journal on Discrete Mathematics, 25(4):1615-1651, 2011.
-
Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué. Maximal independent sets and maximal matchings in series-parallel and related graph classes. The Electronic Journal of Combinatorics, 27(P1.5), 2020.
-
Michael Drmota, Lander Ramos, and Juanjo Rué. Subgraph statistics in subcritical graph classes. Random Structures & Algorithms, 51(4):631-673, 2017.
-
Julia Ehrenmüller and Juanjo Rué. Spanning trees in random series-parallel graphs. Advances in Applied Mathematics, 75:18-55, 2016.
-
Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009.
-
Agelos Georgakopoulos and Stephan Wagner. Subcritical graph classes containing all planar graphs. Combinatorics, Probability and Computing, 27(5):763-773, 2018.
-
Hsien-Kuei Hwang. On convergence rates in the central limit theorems for combinatorial structures. European Journal of Combinatorics, 19(3):329-343, 1998.
-
Olav Kallenberg. Foundations of Modern Probability. Probability and its Applications. Springer-Verlag, New York, second edition, 2002.
-
Konstantinos Panagiotou, Benedikt Stufler, and Kerstin Weller. Scaling limits of random graphs from subcritical graph classes. The Annals of Probability, 44(5):3291-3334, 2016.