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:

Full text arXiv 2210.15538: pdf, ps.