-variable first-order logic of uniform attachment random graphs

DOI10.1016/J.DISC.2022.112802MaRDI QIDQ2113354zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicpebble gameuniform attachment graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Paths and cycles (05C38) Games on graphs (graph-theoretic aspects) (05C57) Zero-one laws (60F20) Games involving graphs (91A43) Classical first-order logic (03B10) Basic properties of first-order languages and structures (03C07)

Abstract: We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with $m$ edges joining the new vertex with $m$ different vertices chosen uniformly at random from $1,ldots,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m-2$ variables.

Recommendations

• \( \gamma \)-variable first-order logic of preferential attachment random graphs
• On the convergence of probabilities of first-order sentences for recursive random graph models
• First-order zero-one law for the uniform model of the random graph
• Zero-one laws for sentences with \(k\) variables
• Random graphs with bounded maximum degree: asymptotic structure and a logical limit law

Cites work

• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 887782 (Why is no real title available?)
• scientific article; zbMATH DE number 1409903 (Why is no real title available?)
• Diameter of P.A. random graphs with edge-step functions
• Elements of finite model theory.
• First-order zero-one law for the uniform model of the random graph
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Logical limit laws for minor-closed classes of graphs
• MSO 0-1 law for recursive random trees
• MSO zero-one laws on random labelled acyclic graphs
• On symmetry of uniform and preferential attachment graphs
• Probabilities on finite models
• Random Graph Processes with Degree Restrictions
• 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
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• Threshold spectra via the Ehrenfeucht game
• Zero-One Laws for Sparse Random Graphs

Cited in

(2)

• On the convergence of probabilities of first-order sentences for recursive random graph models
• \( \gamma \)-variable first-order logic of preferential attachment random graphs

This page was built for publication: \(\gamma\)-variable first-order logic of uniform attachment random graphs

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