γ-variable first-order logic of preferential attachment random graphs

2021/08/18 by Yury Malyshkin, Malyshkin, Yury
Computer Science · Mathematics · #Distributed systems and fault tolerance #Formal Methods in Verification #Interconnection Networks and Systems #math.PR #msc:05C80

paper · pdf · doi:10.48550/arxiv.2108.08116

arxiv created 2021/08/18 · arxiv updated 2021/08/19

Abstract

We study logical limit laws for preferential attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time 1, we start with vertices 0,1 and m edges between them. At step n+1 the vertex n+1 is introduced together with m edges joining the new vertex with m vertices chosen from 1,…,n independently with probabilities proportional to their degrees plus a positive parameter δ. We prove that this random graph obeys the convergence law for first-order sentences with at most m-2 variables.

Related

• γ-variable first-order logic of uniform attachment random graphs
• First-order logic of uniform attachment random graphs with a given degree
• A logical limit law for the sequential model of preferential attachment graphs
• Logical convergence laws via stochastic approximation and Markov processes
• Joint degree distributions of preferential attachment random graphs