Logical properties of random graphs from small addable classes

zbMATH Open1475.03085arXiv1707.02081MaRDI QIDQ5227515FDOQ5227515

Authors: Anuj Dawar, Eryk Kopczyński 

Publication date: 6 August 2019

Abstract: We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of tree-width at most $k$ and the class of connected graphs excluding the $k$-clique as a minor. In each of these cases, dropping the connectivity requirement leads to a class where the zero-one law fails but a convergence law for MSO still holds.

Full work available at URL: https://arxiv.org/abs/1707.02081

Recommendations

• Logical limit laws for minor-closed classes of graphs
• scientific article; zbMATH DE number 5130821
• Random graphs from a minor-closed class
• scientific article; zbMATH DE number 1072412
• Connectivity of addable graph classes
• Infinitary logics and very sparse random graphs
• Connectivity for Bridge-addable monotone graph classes
• Random graphs with bounded maximum degree: asymptotic structure and a logical limit law
• Connectivity of random addable graphs
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

zbMATH Keywords

first-order logiczero-one lawslimit lawrandom planar graphssmooth addable classes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Model theory of finite structures (03C13)

Cites Work

• Probabilities on finite models
• Elements of finite model theory.
• Random graphs from a minor-closed class
• Random planar graphs
• Title not available (Why is that?)
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Title not available (Why is that?)
• Algorithmic uses of the Feferman-Vaught theorem
• Title not available (Why is that?)
• 0-1 laws and decision problems for fragments of second-order logic
• Generating labeled planar graphs uniformly at random
• Finite Model Theory on Tame Classes of Structures
• Infinitary logics and 0-1 laws
• Properties of Almost All Graphs and Generalized Quantifiers
• MSO zero-one laws on random labelled acyclic graphs
• Logical limit laws for minor-closed classes of graphs

Cited In (5)

• Logical limit laws for minor-closed classes of graphs
• Preface to the special issue of Permutation Patterns 2021 (PP2021)
• Logical limit laws for layered permutations and related structures
• Axiomatizing rectangular grids with no extra non-unary relations
• On zero-one and convergence laws for graphs embeddable on a fixed surface

This page was built for publication: Logical properties of random graphs from small addable classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5227515)