6 citations · 8 across the 5 of their papers we have counts for
16 papers
Large cycles in generalized Johnson graphs
Vladislav Kozhevnikov, Maksim Zhukovskii
We count cycles of an unbounded length in generalized Johnson graphs. Asymptotics of the number of such cycles is obtained for certain growth rates of the cycle length.
Maximum induced forests in random graphs
Maria Krivoshapko, Maksim Zhukovskii
We prove that with high probability maximum sizes of induced forests in dense binomial random graphs are concentrated in two consecutive values.
Large cycles in random generalized Johnson graphs
Vladislav Kozhevnikov, Andrey Raigorodskii, Maksim Zhukovskii
This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are ob…
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…
Maximum sparse induced subgraphs of the binomial random graph with given number of edges
Dmitry Kamaldinov, Arkadiy Skorkin, Maksim Zhukovskii
We prove that a.a.s. the maximum size of an induced subtree of the binomial random graph is concentrated in 2 consecutive points. We also prove that, given a non-negative…
Zero-one laws for existential first order sentences of bounded quantifier depth
Moumanti Podder, Maksim Zhukovskii
For any fixed positive integer , let denote the smallest such that the random graph sequence does not satisfy the z…