MODNET

Research Training Network in Model Theory

Publications > Preprint server > Preprint Number 2289
Preprint Number 2289
2289. Y.A. Malyshkin First-order logic of uniform attachment random graphs with a given
degree E-mail: Submission date: 27 October 2022 Abstract: 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: |

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