Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 2289

Preprint Number 2289

Previous Next Preprint server

2289. Y.A. Malyshkin
First-order logic of uniform attachment random graphs with a given degree

Submission date: 27 October 2022


In this paper, we prove the first-order convergence law for the uniform attachment random graph with almost all vertices having the same degree. In the considered model, vertices and edges are introduced recursively: at time m+1 we start with a complete graph on m+1 vertices. At step n+1 the vertex n+1 is introduced together with m edges joining the new vertex with m vertices chosen uniformly from those vertices of 1, ... ,n, whom degree is less then d=2m. To prove the law, we describe the dynamics of the logical equivalence class of the random graph using Markov chains. The convergence law follows from the existence of a limit distribution of the considered Markov chain.

Mathematics Subject Classification: 03C13, 05C80

Keywords and phrases:

Full text arXiv 2210.15538: pdf, ps.

Last updated: November 12 2022 22:07 Please send your corrections to: