Maksim Zhukovskii

activity

20232026

collaborators

22 papers

math.CO2026

A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs

Asaf Cohen Antonir, Ilay Hoshen, Maksim Zhukovskii

Let $X_{H}$ denote the number of copies of a fixed graph $H$ in $G_{n, p}$ . Gilmer and Kopparty conjectured that $X_{H}$ satisfies a local central limit theorem (LCLT) provided that $H…

math.CO2026

Universality in random graphs via optimal linking systems: trees and beyond

Asaf Cohen Antonir, Lyuben Lichev, Maksim Zhukovskii

We develop a framework for proving universality results in sparse random graphs. As a first application, we show that there exists an absolute constant $C > 1$ such that, with high p…

cs.DC2026

What can be computed in average anonymous networks?

Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii

We study what deterministic distributed algorithms can compute on random input graphs in extremely weak models of distributed computing: all nodes are anonymous, and in each commun…

math.CO2026

Canonical labelling of random regular graphs

Mikhail Isaev, Tamás Makai, Brendan McKay +3

We prove that whenever $d = d (n) \to \infty$ and $n - d \to \infty$ as $n \to \infty$ , then with high probability for any non-trivial initial colouring, the colour refinement algorithm disti…

math.PR2025

Diameter and mixing time of the giant component in the percolated hypercube

Michael Anastos, Sahar Diskin, Lyuben Lichev +1

We consider bond percolation on the $d$ -dimensional binary hypercube with $p = c / d$ for fixed $c > 1$ . We prove that the typical diameter of the giant component $L_{1}$ is of order $Θ(d)…

math.CO2025

Weak saturation numbers of large complete bipartite graphs

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}) ∖ E (G)$ such that, when added one at a t…