Logical limit laws for minor-closed classes of graphs
From MaRDI portal
Publication:1745738
DOI10.1016/j.jctb.2017.12.002zbMath1384.05144arXiv1401.7021OpenAlexW2964003570MaRDI 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
Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83) Zero-one laws (60F20) Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07)
Related Items (9)
Logical properties of random graphs from small addable classes ⋮ Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Limiting probabilities of first order properties of random sparse graphs and hypergraphs ⋮ Unnamed Item ⋮ Logical laws for short existential monadic second-order sentences about graphs ⋮ MSO 0-1 law for recursive random trees ⋮ The first order convergence law fails for random perfect graphs ⋮ DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS ⋮ \(\gamma\)-variable first-order logic of uniform attachment random graphs
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Logical limit laws for minor-closed classes of graphs
