m-variable first-order logic of uniform attachment random graphs.
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
15
References
0
Citations
NaN
KQI