Loading...
Loading...

Go to the content (press return)

Subgraph statistics in subcritical graph classes

Author
Drmota, M.; Ramos, L.; Rue, J.
Type of activity
Journal article
Journal
Random structures and algorithms
Date of publication
2017-12
Volume
51
Number
4
First page
631
Last page
673
DOI
https://doi.org/10.1002/rsa.20721 Open in new window
Repository
http://hdl.handle.net/2117/108598 Open in new window
https://arxiv.org/pdf/1512.08889.pdf Open in new window
URL
https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20721 Open in new window
Abstract
Let H be a fixed graph and math formula a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in math formula of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]...
Citation
Drmota, M., Ramos, L., Rue, J. Subgraph statistics in subcritical graph classes. "Random structures and algorithms", 1 Abril 2017, p. 1-43.
Keywords
analytic combinatorics, generating functions, random graphs, series-parallel graphs, subcritical graph classes
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments