Logical properties of random graphs from small addable classes

MaRDI QIDQ5227515zbMATH OpenFDO

Authors Anuj Dawar, Eryk Kopczyński

Publication date 6 August 2019

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5130821 (Why is no real title available?)
• scientific article; zbMATH DE number 1146225 (Why is no real title available?)
• scientific article; zbMATH DE number 6157246 (Why is no real title available?)
• 0-1 laws and decision problems for fragments of second-order logic
• Algorithmic uses of the Feferman-Vaught theorem
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Elements of finite model theory.
• Finite Model Theory on Tame Classes of Structures
• Generating labeled planar graphs uniformly at random
• Infinitary logics and 0-1 laws
• Logical limit laws for minor-closed classes of graphs
• MSO zero-one laws on random labelled acyclic graphs
• Probabilities on finite models
• Properties of Almost All Graphs and Generalized Quantifiers
• Random graphs from a minor-closed class
• Random planar 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)