Maksim Zhukovskii

collaborators

12 papers

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…

math.CO2026

New bounds for the optimal density of covering single-insertion codes via the TurÃ¡n density

Oleg Pikhurko, Oleg Verbitsky, Maksim Zhukovskii

We prove that the density of any covering single-insertion code $C \subseteq X^{r}$ over the $n$ -symbol alphabet $X$ cannot be smaller than $1/ r + I^´_{r}$ for some positive real $I^´_{r}$ no…

math.PR2026

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…

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.CO2025

Saturation in Random Hypergraphs

Sahar Diskin, Ilay Hoshen, DÃ¡niel KorÃ¡ndi +2

Let $K_{n}^{r}$ be the complete $r$ -uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n] := {1, 2, ..., n}$ and whose edge set is $(r [ n ])$ . We form…