Maksim Zhukovskii
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Maksim Zhukovskii has a total of 98 co-authors. Here are the top co-authors by number of shared publications:
- Michael Krivelevich
Tel Aviv University
5 shared publications - Oleg Verbitsky
Institut fr Informatik, Humboldt-Universitt zu Berlin, Berlin, Germany
5 shared publications - A. D. Matushkin
Moscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Russia
4 shared publications - John Sylvester
Department of Computer Science University of Liverpool UK
4 shared publications - Yury Malyshkin
Moscow Institute of Physics and Technology
4 shared publications - Andrey Kupavskii
Moscow Institute of Physics and Technology
3 shared publications
Latest Publications
- 26 October 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-56
FIRST-ORDER DISTINGUISHABILITY OF SPARSE RANDOM GRAPHS
We study the problem of distinguishing between two independent samples $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 of a binomial random graph $G(n,p)$ upper G left parenthesis n comma p right parenthesis by first-order (FO) sentences. Shelah and Spencer proved that, for a constant $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , $G(n,n^{-\alpha })$ upper G left parenthesis n comma n Superscript negative alpha Baseline right parenthesis obeys FO zero-one law if and only if $\alpha $ alpha is irrational. Therefore, for irrational $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , any fixed FO sentence does not distinguish between $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 with asymptotical probability 1 (w.h.p.) as $n\to \infty $ n right arrow infinity . We show that the minimum quantifier depth $\mathbf {k}_{\alpha }$ bold k Subscript alpha of an FO sentence $\varphi =\varphi (\mathbf {G}_n^1,\mathbf {G}_n^2)$ phi equals phi left parenthesis bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 Baseline right parenthesis distinguishing between $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 depends on how closely $\alpha $ alpha can be approximated by rationals: • for all non-Liouville $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , $\mathbf {k}_{\alpha }=\Omega (\ln \ln \ln n)$ bold k Subscript alpha Baseline equals normal upper Omega left parenthesis ln ln ln n right parenthesis w.h.p.; • there are irrational $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis with $\mathbf {k}_{\alpha }$ bold k Subscript alpha that grow arbitrarily slowly w.h.p.; • $\mathbf {k}_{\alpha }=O_p(\frac {\ln n}{\ln \ln n})$ bold k Subscript alpha Baseline equals upper O Subscript p Baseline left parenthesis StartFraction ln n Over ln ln n EndFraction right parenthesis for all $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis . The main ingredients in our proofs are a novel randomized algorithm that generates asymmetric strictly balanced graphs as well as a new method to study symmetry groups of randomly perturbed graphs.- 26 October 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-56
FIRST-ORDER DISTINGUISHABILITY OF SPARSE RANDOM GRAPHS
We study the problem of distinguishing between two independent samples $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 of a binomial random graph $G(n,p)$ upper G left parenthesis n comma p right parenthesis by first-order (FO) sentences. Shelah and Spencer proved that, for a constant $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , $G(n,n^{-\alpha })$ upper G left parenthesis n comma n Superscript negative alpha Baseline right parenthesis obeys FO zero-one law if and only if $\alpha $ alpha is irrational. Therefore, for irrational $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , any fixed FO sentence does not distinguish between $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 with asymptotical probability 1 (w.h.p.) as $n\to \infty $ n right arrow infinity . We show that the minimum quantifier depth $\mathbf {k}_{\alpha }$ bold k Subscript alpha of an FO sentence $\varphi =\varphi (\mathbf {G}_n^1,\mathbf {G}_n^2)$ phi equals phi left parenthesis bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 Baseline right parenthesis distinguishing between $\mathbf {G}_n^1,\mathbf {G}_n^2$ bold upper G Subscript n Superscript 1 Baseline comma bold upper G Subscript n Superscript 2 depends on how closely $\alpha $ alpha can be approximated by rationals: • for all non-Liouville $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , $\mathbf {k}_{\alpha }=\Omega (\ln \ln \ln n)$ bold k Subscript alpha Baseline equals normal upper Omega left parenthesis ln ln ln n right parenthesis w.h.p.; • there are irrational $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis with $\mathbf {k}_{\alpha }$ bold k Subscript alpha that grow arbitrarily slowly w.h.p.; • $\mathbf {k}_{\alpha }=O_p(\frac {\ln n}{\ln \ln n})$ bold k Subscript alpha Baseline equals upper O Subscript p Baseline left parenthesis StartFraction ln n Over ln ln n EndFraction right parenthesis for all $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis . The main ingredients in our proofs are a novel randomized algorithm that generates asymmetric strictly balanced graphs as well as a new method to study symmetry groups of randomly perturbed graphs.- Open Access
- 7 September 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (2)
Majority Dynamics on Finite Trees
For an arbitrary finite tree , we find the exact value of the worst‐case stabilization time of majority dynamics on . We also prove that for a perfect rooted cubic tree with diameter and uniformly random initial opinions, the dynamics stabilizes in time with high probability.
- 7 September 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (2)
Open AccessMajority Dynamics on Finite Trees
For an arbitrary finite tree , we find the exact value of the worst‐case stabilization time of majority dynamics on . We also prove that for a perfect rooted cubic tree with diameter and uniformly random initial opinions, the dynamics stabilizes in time with high probability.
- Open Access
- 7 September 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (2) , e70093
On the Threshold for Triangulations Inside Convex Polygons
Start with a large convex polygon and add all other edges inside independently with probability . At what critical threshold do triangulations of the polygon begin to appear? The first author and Gravner asked this question and observed that , using the relationship with the Catalan numbers and a coupling with oriented site percolation on . More recently, Archer, Hartarsky, the first author, Olesker‐Taylor, Schapira, and Valesin proved that , where is the Catalan exponential growth rate and is the critical threshold for oriented percolation. The upper bound is strict, but nonquantitative and follows by a renormalization argument. In this work, we show that using a simple ear clipping algorithm, which can be analyzed by comparing with random walks with negative drift. This bound is closer to the truth (perhaps near 0.4) and shows that most configurations of edges inside large convex polygons contain triangulations.
- 7 September 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (2) , e70093
Open AccessOn the Threshold for Triangulations Inside Convex Polygons
Start with a large convex polygon and add all other edges inside independently with probability . At what critical threshold do triangulations of the polygon begin to appear? The first author and Gravner asked this question and observed that , using the relationship with the Catalan numbers and a coupling with oriented site percolation on . More recently, Archer, Hartarsky, the first author, Olesker‐Taylor, Schapira, and Valesin proved that , where is the Catalan exponential growth rate and is the critical threshold for oriented percolation. The upper bound is strict, but nonquantitative and follows by a renormalization argument. In this work, we show that using a simple ear clipping algorithm, which can be analyzed by comparing with random walks with negative drift. This bound is closer to the truth (perhaps near 0.4) and shows that most configurations of edges inside large convex polygons contain triangulations.
- Open Access
- 25 June 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (5) , 1-11
A large hole in pseudo-random graphs
We show that there exist constants delta 1 comma delta 2 greater than 0 $\delta _1,\delta _2\gt 0$ such that if upper G $G$ is an left parenthesis n comma d comma lamda right parenthesis $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 $\lambda /d\le \delta _1$ , then upper G $G$ contains an induced cycle of length at least delta 2 n divided by d $\delta _2n/d$ . We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such upper G $G$ is at least exponential in n log d divided by d $n\log d/d$ , and further demonstrate that this is tight up to a constant factor in the exponent.- 25 June 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (5) , 1-11
Open AccessA large hole in pseudo-random graphs
We show that there exist constants delta 1 comma delta 2 greater than 0 $\delta _1,\delta _2\gt 0$ such that if upper G $G$ is an left parenthesis n comma d comma lamda right parenthesis $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 $\lambda /d\le \delta _1$ , then upper G $G$ contains an induced cycle of length at least delta 2 n divided by d $\delta _2n/d$ . We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such upper G $G$ is at least exponential in n log d divided by d $n\log d/d$ , and further demonstrate that this is tight up to a constant factor in the exponent. - Open Access
- 23 June 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 68 (4)
Maximum Induced Trees and Forests of Bounded Degree in Random Graphs
The asymptotic behavior of the maximum sizes of induced trees and forests has been studied extensively in the last few decades, though the overall picture is far from being complete. In this paper, we close several significant gaps: (1) We prove 2‐point concentration of the maximum sizes of an induced forest and an induced tree with maximum degree at most in dense binomial random graphs with constant probability . (2) We show concentration in an explicit interval of size for the maximum size of an induced forest with maximum degree at most for . Our proofs rely on both a fairly standard second moment approach, with the probabilistic part involving Talagrand's concentration inequality and the analytical part involving saddle‐point analysis. Additionally, we present new results on the enumeration of labeled trees and forests, which might be of independent interest.
- 23 June 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 68 (4)
Open AccessMaximum Induced Trees and Forests of Bounded Degree in Random Graphs
The asymptotic behavior of the maximum sizes of induced trees and forests has been studied extensively in the last few decades, though the overall picture is far from being complete. In this paper, we close several significant gaps: (1) We prove 2‐point concentration of the maximum sizes of an induced forest and an induced tree with maximum degree at most in dense binomial random graphs with constant probability . (2) We show concentration in an explicit interval of size for the maximum size of an induced forest with maximum degree at most for . Our proofs rely on both a fairly standard second moment approach, with the probabilistic part involving Talagrand's concentration inequality and the analytical part involving saddle‐point analysis. Additionally, we present new results on the enumeration of labeled trees and forests, which might be of independent interest.
- 26 November 2025
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (2) , 178-206
Canonization of a random circulant graph by counting walks
It is well known that almost all graphs are canonizable by a simple combinatorial routine known as colour refinement, also referred to as the 1-dimensional Weisfeiler–Leman algorithm. With high probability, this method assigns a unique label to each vertex of a random input graph and, hence, it is applicable only to asymmetric graphs. The strength of combinatorial refinement techniques becomes a subtle issue if the input graphs are highly symmetric. We prove that the combination of colour refinement and vertex individualization yields a canonical labelling for almost all circulant digraphs (i.e., Cayley digraphs of a cyclic group). This result provides first evidence of good average-case performance of combinatorial refinement within the class of vertex-transitive graphs. Remarkably, we do not even need the full power of the colour refinement algorithm. We show that the canonical label of a vertex $v$ can be obtained just by counting walks of each length from $v$ to an individualized vertex. Our analysis also implies that almost all circulant graphs are compact in the sense of Tinhofer, that is, their polytops of fractional automorphisms are integral. Finally, we show that a canonical Cayley representation can be constructed for almost all circulant graphs by the more powerful 2-dimensional Weisfeiler–Leman algorithm.- 26 November 2025
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (2) , 178-206
Canonization of a random circulant graph by counting walks
It is well known that almost all graphs are canonizable by a simple combinatorial routine known as colour refinement, also referred to as the 1-dimensional Weisfeiler–Leman algorithm. With high probability, this method assigns a unique label to each vertex of a random input graph and, hence, it is applicable only to asymmetric graphs. The strength of combinatorial refinement techniques becomes a subtle issue if the input graphs are highly symmetric. We prove that the combination of colour refinement and vertex individualization yields a canonical labelling for almost all circulant digraphs (i.e., Cayley digraphs of a cyclic group). This result provides first evidence of good average-case performance of combinatorial refinement within the class of vertex-transitive graphs. Remarkably, we do not even need the full power of the colour refinement algorithm. We show that the canonical label of a vertex $v$ can be obtained just by counting walks of each length from $v$ to an individualized vertex. Our analysis also implies that almost all circulant graphs are compact in the sense of Tinhofer, that is, their polytops of fractional automorphisms are integral. Finally, we show that a canonical Cayley representation can be constructed for almost all circulant graphs by the more powerful 2-dimensional Weisfeiler–Leman algorithm.- Open Access
- 19 September 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (5) , 1-18
Weak saturation rank: a failure of the linear algebraic approach to weak saturation
Given a graph F and a positive integer n , the weak F -saturation number $${\textrm{wsat}}(K_n,F)$$ is the minimum number of edges in a graph H on n vertices such that the edges missing in H can be added, one at a time, so that every edge creates a copy of F . Kalai in 1985 introduced a linear algebraic approach that became one of the most efficient tools to prove lower bounds on weak saturation numbers. Let W be a vector space spanned by vectors w ( e ) assigned to edges e of $$K_n$$ . Suppose that, for every copy $$F'\subset K_n$$ of F , there exist non-zero scalars $$\lambda _e$$ , $$e\in E(F')$$ , satisfying $$\sum _{e\in E(F')}\lambda _e w(e)=0$$ . Then $$\textrm{dim}W\le {\textrm{wsat}}(K_n,F)$$ . In this paper, we prove limitations of this approach: we find infinitely many F such that, for every vector space W as above, $$\textrm{dim}W<{\textrm{wsat}}(K_n,F)$$ . We also introduce a modification of this approach that yields tight lower bounds even when the original direct approach is insufficient. Finally, we generalise our results to random graphs, complete multipartite graphs, and hypergraphs.- 19 September 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (5) , 1-18
Open AccessWeak saturation rank: a failure of the linear algebraic approach to weak saturation
Given a graph F and a positive integer n , the weak F -saturation number $${\textrm{wsat}}(K_n,F)$$ is the minimum number of edges in a graph H on n vertices such that the edges missing in H can be added, one at a time, so that every edge creates a copy of F . Kalai in 1985 introduced a linear algebraic approach that became one of the most efficient tools to prove lower bounds on weak saturation numbers. Let W be a vector space spanned by vectors w ( e ) assigned to edges e of $$K_n$$ . Suppose that, for every copy $$F'\subset K_n$$ of F , there exist non-zero scalars $$\lambda _e$$ , $$e\in E(F')$$ , satisfying $$\sum _{e\in E(F')}\lambda _e w(e)=0$$ . Then $$\textrm{dim}W\le {\textrm{wsat}}(K_n,F)$$ . In this paper, we prove limitations of this approach: we find infinitely many F such that, for every vector space W as above, $$\textrm{dim}W<{\textrm{wsat}}(K_n,F)$$ . We also introduce a modification of this approach that yields tight lower bounds even when the original direct approach is insufficient. Finally, we generalise our results to random graphs, complete multipartite graphs, and hypergraphs. - Open Access
On the threshold for triangulations inside convex polygons
Start with a large convex polygon and add all other edges inside independently with probability $p$. At what critical threshold $p_c$ do triangulations of the polygon begin to appear? The first author and Gravner asked this question, and observed that $p_c=Θ(1)$, using the relationship with the Catalan numbers and a coupling with oriented site percolation on ${\mathbb Z}^2$. More recently, Archer, Hartarsky, the first author, Olesker-Taylor, Schapira and Valesin proved that $1/4<p_c<p_c^o$, where $1/4$ is the Catalan exponential growth rate and $p_c^o$ is the critical threshold for oriented percolation. The upper bound is strict, but non-quantitative, and follows by a renormalization argument. We show that $p_c<1/2$ using a simple ear clipping algorithm, which can be analyzed using the gambler's ruin problem. This bound is closer to the truth (perhaps near $0.4$) and shows that most configurations of edges inside large convex polygons contain triangulations.Open AccessOn the threshold for triangulations inside convex polygons
Start with a large convex polygon and add all other edges inside independently with probability $p$. At what critical threshold $p_c$ do triangulations of the polygon begin to appear? The first author and Gravner asked this question, and observed that $p_c=Θ(1)$, using the relationship with the Catalan numbers and a coupling with oriented site percolation on ${\mathbb Z}^2$. More recently, Archer, Hartarsky, the first author, Olesker-Taylor, Schapira and Valesin proved that $1/4<p_c<p_c^o$, where $1/4$ is the Catalan exponential growth rate and $p_c^o$ is the critical threshold for oriented percolation. The upper bound is strict, but non-quantitative, and follows by a renormalization argument. We show that $p_c<1/2$ using a simple ear clipping algorithm, which can be analyzed using the gambler's ruin problem. This bound is closer to the truth (perhaps near $0.4$) and shows that most configurations of edges inside large convex polygons contain triangulations. - Open Access
Weak saturation numbers of large complete bipartite graphs
An $n$-vertex graph $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ and there exists an ordering of all edges in $E(K_n) \setminus E(G)$ such that, when added one at a time, each edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ is called the weak saturation number $\mathrm{wsat}(n, F)$. We obtain exact values and new bounds for $\mathrm{wsat}(n, K_{s,t})$ in the previously unaddressed range $s+t < n < 3t-3$, where $3\leq s\leq t$. To prove lower bounds, we introduce a new method that takes into account connectivity properties of subgraphs of a complement $G'$ to a weakly saturated graph $G$. We construct an auxiliary hypergraph and show that a linear combination of its parameters always increases in the process of the deletion of edges of $G'$. This gives a lower bound which is tight, up to an additive constant.Open AccessWeak saturation numbers of large complete bipartite graphs
An $n$-vertex graph $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ and there exists an ordering of all edges in $E(K_n) \setminus E(G)$ such that, when added one at a time, each edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ is called the weak saturation number $\mathrm{wsat}(n, F)$. We obtain exact values and new bounds for $\mathrm{wsat}(n, K_{s,t})$ in the previously unaddressed range $s+t < n < 3t-3$, where $3\leq s\leq t$. To prove lower bounds, we introduce a new method that takes into account connectivity properties of subgraphs of a complement $G'$ to a weakly saturated graph $G$. We construct an auxiliary hypergraph and show that a linear combination of its parameters always increases in the process of the deletion of edges of $G'$. This gives a lower bound which is tight, up to an additive constant. - Open Access
Majority dynamics on finite trees
For an arbitrary finite tree $T$, we find the exact value of the wort-case stabilisation time of majority dynamics on $T$. We also prove that for a perfect rooted cubic tree $T$ with diameter $D$ and uniformly random initial opinions, the dynamics stabilises in time $τ\in(D/4,D/3)$ with high probability.Open AccessMajority dynamics on finite trees
For an arbitrary finite tree $T$, we find the exact value of the wort-case stabilisation time of majority dynamics on $T$. We also prove that for a perfect rooted cubic tree $T$ with diameter $D$ and uniformly random initial opinions, the dynamics stabilises in time $τ\in(D/4,D/3)$ with high probability.