Asymptotic Properties of Some Minor-Closed Classes of Graphs
From MaRDI portal
Abstract: Let A be a minor-closed class of labelled graphs, and let G_n be a random graph sampled uniformly from the set of n-vertex graphs of A. When n is large, what is the probability that G_n is connected? How many components does it have? How large is its biggest component? Thanks to the work of McDiarmid and his collaborators, these questions are now solved when all excluded minors are 2-connected. Using exact enumeration, we study a collection of classes A excluding non-2-connected minors, and show that their asymptotic behaviour may be rather different from the 2-connected case. This behaviour largely depends on the nature of dominant singularity of the generating function C(z) that counts connected graphs of A. We classify our examples accordingly, thus taking a first step towards a classification of minor-closed classes of graphs. Furthermore, we investigate a parameter that has not received any attention in this context yet: the size of the root component. It follows non-gaussian limit laws (beta and gamma), and clearly deserves a systematic investigation.
Recommendations
- Asymptotic properties of some minor-closed classes of graphs
- Growth constants of minor-closed classes of graphs
- On random graphs from a minor-closed class
- On the purity of minor-closed classes of graphs
- Random graphs from a minor-closed class
- Logical limit laws for minor-closed classes of graphs
- Strengthening Erdős -- Pósa property for minor-closed graph classes
- Asymptotic values of minimal graphs in a disc
- Asymptotic behaviour of minimal graphs over exterior domains
- Asymptotic density of graphs excluding disconnected minors
Cites work
- Analytic combinatorics
- Asymptotic Methods in Enumeration
- Asymptotic study of subcritical graph classes
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Central and local limit theorems for the coefficients of polynomials of binomial type
- Connectivity for Bridge-addable monotone graph classes
- Degree distribution in random planar graphs
- Discrete mathematics: topics in combinatorics
- Extended admissible functions and Gaussian limiting distributions
- Graph classes with given 3-connected components: asymptotic enumeration and random graphs
- Growth constants of minor-closed classes of graphs
- Largest component in random combinatorial structures
- Marking in combinatorial constructions: Generating functions and limiting distributions
- On graphs with few disjoint \(t\)-star minors
- On the connectivity of random graphs from addable classes
- On the Lambert \(w\) function
- Operational methods and the coefficients of certain power series
- Proper minor-closed families are small
- Random graphs from a minor-closed class
- Random maps, coalescing saddles, singularity analysis, and Airy phenomena
- Random planar graphs
- The degree sequence of random graphs from subcritical classes
- The number of connected sparsely edged graphs
Cited in
(13)- Logical limit laws for minor-closed classes of graphs
- Graph classes with given 3-connected components: asymptotic enumeration and random graphs
- Graph classes with given 3-connected components: asymptotic counting and critical phenomena
- Random graphs from a minor-closed class
- Random graphs from a weighted minor-closed class
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- On random graphs from a minor-closed class
- Asymptotic properties of some minor-closed classes of graphs
- The complexity of learning minor closed graph classes
- Densities of minor-closed graph families
- Pendant appearances and components in random graphs from structured classes
- Enumerations, forbidden subgraph characterizations, and the split-decomposition
- Growth constants of minor-closed classes of graphs
This page was built for publication: Asymptotic Properties of Some Minor-Closed Classes of Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191199)
