-variable first-order logic of uniform attachment random graphs

DOI10.1016/J.DISC.2022.112802zbMATH Open1491.05171arXiv2008.13140OpenAlexW4206296400MaRDI QIDQ2113354FDOQ2113354

Authors: Yanyan Li 

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Probabilities on finite models
• The strange logic of random graphs
• The degree sequence of a scale-free random graph process
• Zero-One Laws for Sparse Random Graphs
• Random graphs: models and asymptotic characteristics
• Elements of finite model theory.
• Threshold spectra via the Ehrenfeucht game
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• Random Graph Processes with Degree Restrictions
• Title not available (Why is that?)
• The logic of random regular graphs
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• On symmetry of uniform and preferential attachment graphs
• Title not available (Why is that?)
• Diameter of P.A. random graphs with edge-step functions
• MSO zero-one laws on random labelled acyclic graphs
• Title not available (Why is that?)
• First-order zero-one law for the uniform model of the random graph
• Logical limit laws for minor-closed classes of graphs
• MSO 0-1 law for recursive random trees

Cited In (2)

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

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)