6 citations · 6 across the 6 of their papers we have counts for
6 papers
Reconstruction of graph colourings
Yury Demidovich, Yaroslav Panichkin, Maksim Zhukovskii
A -deck of a (coloured) graph is a multiset of its induced -vertex subgraphs. Given a graph , when is it possible to reconstruct with high probability a uniformly random c…
Maximum number of symmetric extensions in the random graph
Stepan Vakhrushev, Maksim Zhukovskii
It is known that after an appropriate rescaling the maximum degree of the binomial random graph converges in distribution to a Gumbel random variable. The same holds true for the m…
Weak saturation in graphs: a combinatorial approach
Nikolai Terekhov, Maksim Zhukovskii
The weak saturation number is the minimum number of edges in a graph on vertices such that all the missing edges can be activated sequentially so that each…
Saturation numbers of bipartite graphs in random graphs
Meysam Miralaei, Ali Mohammadian, Behruz Tayfeh-Rezaie +1
For a given graph , the -saturation number of a graph , denoted by , is the minimum number of edges in an edge-maximal -free subgraph of . In 2017, Kor…
On infinite spectra of first order properties of random graphs
M. E. Zhukovskii
In this paper, we study spectra of first order properties of Erdos-Renyi random graph. We proved that minimal quantifier depth of a formula with an infinite spectrum is either 4 or…
Monadic second-order properties of very sparse random graphs
L. B. Ostrovsky, M. E. Zhukovskii
We study asymptotical probabilities of first order and monadic second order properties of Erdos-Renyi random graph G(n,n^{-a}). The random graph obeys FO (MSO) zero-one k-law if fo…