Logical limit laws for minor-closed classes of graphs
From MaRDI portal
Publication:1745738
DOI10.1016/j.jctb.2017.12.002zbMath1384.05144arXiv1401.7021MaRDI QIDQ1745738
Marc Noy, Anusch Taraz, Tobias Müller, Peter Heinig
Publication date: 18 April 2018
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.7021
05C80: Random graphs (graph-theoretic aspects)
05C83: Graph minors
60F20: Zero-one laws
03C13: Model theory of finite structures
03C07: Basic properties of first-order languages and structures
Related Items
Short Monadic Second Order Sentences about Sparse Random Graphs, Unnamed Item, Logical laws for short existential monadic second-order sentences about graphs, DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS, Logical properties of random graphs from small addable classes, Limiting probabilities of first order properties of random sparse graphs and hypergraphs, The first order convergence law fails for random perfect graphs, \(\gamma\)-variable first-order logic of uniform attachment random graphs, MSO 0-1 law for recursive random trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The logic of random regular graphs
- Asymptotic enumeration of labelled graphs by genus
- Random graphs on surfaces
- Growth constants of minor-closed classes of graphs
- Coefficients of functional compositions often grow smoothly
- On random models of finite power and monadic logic
- A logical approach to asymptotic combinatorics I. First order properties
- MSO zero-one laws on random labelled acyclic graphs
- On the connectivity of random graphs from addable classes
- Generating labeled planar graphs uniformly at random
- Asymptotic enumeration and limit laws for graphs of fixed genus
- Proper minor-closed families are small
- A logical approach to asymptotic combinatorics. II: Monadic second-order properties
- Graph classes with given 3-connected components: Asymptotic enumeration and random graphs
- Asymptotic enumeration and limit laws of planar graphs
- Connectivity for Bridge-Addable Monotone Graph Classes
- Asymptotic Properties of Some Minor-Closed Classes of Graphs
- Asymptotic Study of Subcritical Graph Classes
- Random Graphs from a Minor-Closed Class
- K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
- Zero-One Laws for Sparse Random Graphs
- Probabilities on finite models
- 0-1 laws for maps
- Coloring rules for finite trees, and probabilities of monadic second order sentences
- Random Geometric Graphs
- On a paper of Guthrie and Nymann on subsums of infinite series
- Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
- Convergence law for random graphs with specified degree sequence
- The strange logic of random graphs
