m-variable first-order logic of uniform attachment random graphs
Yury Malyshkin, Maksim Evgen'evich Zhukovskii · arXiv (Cornell University) · 2020
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,...,n. We prove that this random graph obeys convergence law for first-order sentences with at most m variables.