38 citations · 74 across the 45 of their papers we have counts for
52 papers
Canonization of a random graph by two matrix-vector multiplications
Oleg Verbitsky, Maksim Zhukovskii
We show that a canonical labeling of a random -vertex graph can be obtained by assigning to each vertex the triple , where is the number of…
Maximum chordal subgraphs of random graphs
Michael Krivelevich, Maksim Zhukovskii
We find asymptotics of the maximum size of a chordal subgraph in a binomial random graph , for and .
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…
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +2
We show that for any natural number , there is a constant and a subgraph-closed class having, for any natural , at most graphs on vertices up to isomorphism, bu…
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…
A Jump of the Saturation Number in Random Graphs?
Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii
For graphs and , the saturation number is the minimum number of edges in an inclusion-maximal -free subgraph of . In 2017, Korándi and Sudakov init…
Sharp thresholds for spanning regular graphs
Maksim Zhukovskii
Let be a constant and let be a -regular graph on with not too many symmetries. By the union bound, the probability threshold for the existence of a spanning…
Tight concentration of star saturation number in random graphs
Sergej Demyanov, Maksim Zhukovskii
For given graphs and , the minimum number of edges in an inclusion-maximal -free subgraph of is called the -saturation number and denoted . For…
On vertex Ramsey graphs with forbidden subgraphs
Sahar Diskin, Ilay Hoshen, Michael Krivelevich +1
A classical vertex Ramsey result due to Nešetřil and Rödl states that given a finite family of graphs , a graph and a positive integer , if every graph $B\in\ma…
Randomly twisted hypercubes -- between structure and randomness
Itai Benjamini, Yotam Dikstein, Renan Gross +1
Twisted hypercubes are generalizations of the Boolean hypercube, obtained by iteratively connecting two instances of a graph by a uniformly random perfect matching. Dudek et al. sh…
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…
A very sharp threshold for first order logic distinguishability of random graphs
Itai Benjamini, Maksim Zhukovskii
In this paper we find an integer such that the minimum number of variables of a first order sentence that distinguishes between two independent uniformly distributed rando…
Global information from local observations of the noisy voter model on a graph
Itai Benjamini, Hagai Helman Tov, Maksim Zhukovskii
We observe the outcome of the discrete time noisy voter model at a single vertex of a graph. We show that certain pairs of graphs can be distinguished by the frequency of repetitio…
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.
Covering three-tori with cubes
Ilya Bogdanov, Oleg Grigoryan, Maksim Zhukovskii
Let be the minimum number of cubes of side needed to cover the unit three-torus . We prove new lower and upper bounds for…
On anti-stochastic properties of unlabeled graphs
Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky +1
We study vulnerability of a uniformly distributed random graph to an attack by an adversary who aims for a global change of the distribution while being able to make only a local c…
Spectrum of FO logic with quantifier depth 4 is finite
Yury Yarovikov, Maksim Zhukovskii
The -spectrum is the set of all such that does not obey the 0-1 law for FO sentences with quantifier depth at most . In this paper, we prove that the mini…
Cycle saturation in random graphs
Yury Demidovich, Arkadiy Skorkin, Maksim Zhukovskii
For a fixed graph the minimum number of edges in an edge-maximal -free subgraph of is called the -saturation number. The asymptotics of the -saturation number of…
Weak saturation stability
Olga Kalinichenko, Maksim Zhukovskii
The paper studies wsat which is the minimum number of edges in a weakly -saturated subgraph of . We prove that wsat is `stable' - remains the same after indep…
EMSO(FO) 0-1 law fails for all dense random graphs
Margarita Akhmejanova, Maksim Zhukovskii
In this paper, we disprove EMSO(FO) convergence law for the binomial random graph for any constant probability . More specifically, we prove that there exists an ex…
Extremal independence in discrete random systems
Mikhail Isaev, Igor Rodionov, Rui-Ray Zhang +1
Let be a sequence of random vectors, where and . Under certain weakly dependence conditions, we prove that the distribut…
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.