MZMaksim Zhukovskii

Maksim Zhukovskii

*This is an algorithmically generated author record based on publicly available information.

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


Maksim Zhukovskii has a total of 98 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • FIRST-ORDER DISTINGUISHABILITY OF SPARSE RANDOM GRAPHS

    by Tal Hershko, Maksim Zhukovskii

    We study the problem of distinguishing between two independent samples G n 1 , G n 2 $\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 ) $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 α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , G ( n , n − α ) $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 α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , any fixed FO sentence does not distinguish between G n 1 , G n 2 $\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 → ∞ $n\to \infty $ n right arrow infinity . We show that the minimum quantifier depth k α $\mathbf {k}_{\alpha }$ bold k Subscript alpha of an FO sentence φ = φ ( G n 1 , G n 2 ) $\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 G n 1 , G n 2 $\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 α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis , k α = Ω ( ln ⁡ ln ⁡ ln ⁡ n ) $\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 α ∈ ( 0 , 1 ) $\alpha \in (0,1)$ alpha element of left parenthesis 0 comma 1 right parenthesis with k α $\mathbf {k}_{\alpha }$ bold k Subscript alpha that grow arbitrarily slowly w.h.p.; • k α = O p ( ln ⁡ n ln ⁡ ln ⁡ n ) $\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 α ∈ ( 0 , 1 ) $\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

    Majority Dynamics on Finite Trees

    by Itai Benjamini, Georgii Zakharov, Maksim Zhukovskii

    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

    On the Threshold for Triangulations Inside Convex Polygons

    by Brett Kolesnik, Georgii Zakharov, Maksim Zhukovskii

    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

    A large hole in pseudo-random graphs

    by Sahar Diskin, Michael Krivelevich, Itay Markbreit, Maksim Zhukovskii

    We show that there exist constants delta 1 comma delta 2 greater than 0 δ 1 , δ 2 > 0 $\delta _1,\delta _2\gt 0$ such that if upper G G $G$ is an left parenthesis n comma d comma lamda right parenthesis ( n , d , λ ) $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 λ / d ≤ δ 1 $\lambda /d\le \delta _1$ , then upper G G $G$ contains an induced cycle of length at least delta 2 n divided by d δ 2 n / 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 $G$ is at least exponential in n log d divided by d n log ⁡ d / d $n\log d/d$ , and further demonstrate that this is tight up to a constant factor in the exponent.

  • Open Access

    Maximum Induced Trees and Forests of Bounded Degree in Random Graphs

    by Margarita Akhmejanova, Vladislav Kozhevnikov, Maksim Zhukovskii

    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.

  • Canonization of a random circulant graph by counting walks

    by Oleg Verbitsky, Maksim Zhukovskii

    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

    Weak saturation rank: a failure of the linear algebraic approach to weak saturation

    by Nikolai Terekhov, Maksim Zhukovskii

    Given a graph F and a positive integer n , the weak F -saturation number $${\textrm{wsat}}(K_n,F)$$ 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$$ K n . Suppose that, for every copy $$F'\subset K_n$$ F ′ ⊂ K n of F , there exist non-zero scalars $$\lambda _e$$ λ e , $$e\in E(F')$$ e ∈ E ( F ′ ) , satisfying $$\sum _{e\in E(F')}\lambda _e w(e)=0$$ ∑ e ∈ E ( F ′ ) λ e w ( e ) = 0 . Then $$\textrm{dim}W\le {\textrm{wsat}}(K_n,F)$$ dim W ≤ 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)$$ dim W < 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

    by Brett Kolesnik, Georgii Zakharov, Maksim Zhukovskii

    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

    by Margarita Akhmejanova, Ilya Vorobyev, Maksim Zhukovskii

    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

    by Itai Benjamini, Georgii Zakharov, Maksim Zhukovskii

    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.