187 citations · 197 across the 10 of their papers we have counts for
11 papers
First-order logic of uniform attachment random graphs with a given degree
Y. A. Malyshkin
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 a…
Logical convergence laws via stochastic approximation and Markov processes
Yury Malyshkin, Maksim Zhukovskii
Since the paper of Kleinberg and Kleinberg, SODA'05, where it was proven that the preferential attachment random graph with degeneracy at least 3 does not obey the first order 0-1…
Preferential attachment with fitness dependent choice
Yury Malyshkin
We study the asymptotic behavior of the maximum degree in the evolving tree model with a choice based on both degree and fitness of a vertex. The tree is constructed in the followi…
-variable first-order logic of uniform attachment random graphs
Yury Malyshkin, Maksim Zhukovskii
We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time , the vertex is intr…
MSO 0-1 law for recursive random trees
Y. A. Malyshkin, M. E. Zhukovskii
We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does no…
Sublinear preferential attachment combined with the growing number of choices
Yury Malyshkin
We prove almost sure convergence of the maximum degree in an evolving graph model combining a growing number of local choices with sublinear preferential attachment. At each step i…