Maksim Zhukovskii

activity

20202026

collaborators

23 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…

math.CO2025

When does a tree activate the random graph?

Asaf Cohen Antonir, Yuval Peled, Asaf Shapira +2

Let $F$ and $G$ be two graphs. A spanning subgraph $H$ of $G$ is called weakly $F$ -saturated if one can add to $H$ the edges of $G ∖ H$ in some order, so that whenever a ne…

math.CO2025

A large hole in pseudo-random graphs

Sahar Diskin, Michael Krivelevich, Itay Markbreit +1

We show that there exist constants $δ_{1}, δ_{2} > 0$ such that if $G$ is an $(n, d, λ)$ -graph with $λ / d \leq δ_{1}$ , then $G$ contains an induced cycle of length at least $δ_{2} n / d$ . We further d…

math.CO2025

Non-isomorphic subgraphs in random graphs

Michael Krivelevich, Maksim Zhukovskii

We establish the asymptotic behaviour of $μ (G (n, p))$ , the number of unlabelled induced subgraphs in the binomial random graph $G (n, p)$ , for almost the entire range of the probabili…

math.CO2024

Tree tilings in random regular graphs

Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii

We show that for every $ε > 0$ there exists a sufficiently large $d_{0} \in N$ such that for every $d \geq d_{0}$ , whp the random $d$ -regular graph $G (n, d)$ contains a $T$ -factor f…

cs.DM2024

Gathering Information about a Graph by Counting Walks from a Single Vertex

Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky +1

We say that a vertex $v$ in a connected graph $G$ is decisive if the numbers of walks from $v$ of each length determine the graph $G$ rooted at $v$ up to isomorphism among all conn…

cs.DM2024

Canonical labelling of sparse random graphs

Oleg Verbitsky, Maksim Zhukovskii

We show that if $p = O (1/ n)$ , then the Erdős-Rényi random graph $G (n, p)$ with high probability admits a canonical labeling computable in time $O (n lo g n)$ . Combined with the previous…

math.CO2024

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 + δ_{r}$ for some positive real $δ_{r}$ not…

math.CO2024

Maximum induced trees and forests of bounded degree in random graphs

Margarita Akhmejanova, Vladislav Kozhevnikov, Maksim Zhukovskii

Asymptotic behaviour of maximum sizes of induced trees and forests has been studied extensively in last decades, though the overall picture is far from being complete. In this pape…

math.CO2024

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

Nikolai Terekhov, Maksim Zhukovskii

Given a graph $F$ and a positive integer $n$ , the weak $F$ -saturation number $wsat (K_{n}, F)$ is the minimum number of edges in a graph $H$ on $n$ vertices such that the edge…

math.CO2024

First order distinguishability of sparse random graphs

Tal Hershko, Maksim Zhukovskii

We study the problem of distinguishing between two independent samples $G_{n}^{1}, G_{n}^{2}$ of a binomial random graph $G (n, p)$ by first order (FO) sentences. Shelah and…

math.CO2024

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…

math.CO2024

Reconstructing random graphs from distance queries

Michael Krivelevich, Maksim Zhukovskii

We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph $G (n, p)$ with constant diameter with high probability. We get a tight…

math.CO2024

Stability of large cuts in random graphs

Ilay Hoshen, Wojciech Samotij, Maksim Zhukovskii

We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If $1/ n ≪ p = 1 - Ω (1)$ , then, with high probability, there is a se…

cs.LO2024

First order complexity of finite random structures

Danila Demin, Maksim Zhukovskii

For a sequence of random structures with $n$ -element domains over a relational signature, we define its first order (FO) complexity as a certain subset in the Banach space $\ell^{\…

math.CO2023

Tight bounds on adjacency labels for monotone graph classes

Édouard Bonnet, Julien Duron, John Sylvester +2

A class of graphs admits an adjacency labeling scheme of size $b (n)$ , if the vertices in each of its $n$ -vertex graphs can be assigned binary strings (called labels) of length $b(n…

cs.CC2023

Canonization of a random circulant graph by counting walks

Oleg Verbitsky, Maksim Zhukovskii

It is well known that almost all graphs are canonizable by a simple combinatorial routine known as color refinement, also referred to as the 1-dimensional Weisfeiler-Leman algorith…

math.CO2020

Tight asymptotics of clique-chromatic numbers of dense random graphs

Yury Demidovich, Maksim Zhukovskii

The clique chromatic number of a graph is the minimum number of colors required to assign to its vertex set so that no inclusion maximal clique is monochromatic. McDiarmid, Mitsche…