MSO 0-1 law for recursive random trees

DOI10.1016/J.SPL.2021.109061MaRDI QIDQ2244503zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 12 November 2021

Published in Statistics \& Probability Letters (Search for Journal in Brave)

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

zbMATH Keywords

0-1 lawmonadic second-order logicpreferential attachment treeuniform attachment tree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20)

Abstract: We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.

Recommendations

• On the convergence of probabilities of first-order sentences for recursive random graph models
• MSO zero-one laws on random labelled acyclic graphs
• scientific article; zbMATH DE number 887782
• On the structure of random unlabelled acyclic graphs.
• 0-1 laws for recursive structures

Cites work

• Coloring rules for finite trees, and probabilities of monadic second order sentences
• Elements of finite model theory.
• First-order zero-one law for the uniform model of the random graph
• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• scientific article; zbMATH DE number 515748 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Logical laws for short existential monadic second-order sentences about graphs
• Logical limit laws for minor-closed classes of graphs
• Monadic second-order properties of very sparse random graphs
• MSO zero-one laws on random labelled acyclic graphs
• On random models of finite power and monadic logic
• Paths in graphs
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• The degree sequence of a scale-free random graph process
• The logic of random regular graphs
• The strange logic of random graphs
• Threshold spectra via the Ehrenfeucht game
• Zero-One Laws for Sparse Random Graphs

Cited in

(5)

• \(\gamma\)-variable first-order logic of uniform attachment random graphs
• \( \gamma \)-variable first-order logic of preferential attachment random graphs
• On the convergence of probabilities of first-order sentences for recursive random graph models
• Deciding sparseness of regular languages of finite trees and infinite words
• Logical convergence laws via stochastic approximation and Markov processes

This page was built for publication: MSO 0-1 law for recursive random trees

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