M. Zhukovskii

activity

20132023

most citedLearning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods

38 citations · 74 across the 45 of their papers we have counts for

collaborators

Showing 2023Show all

9 papers · 1 filter

cs.CC2023

Canonization of a random graph by two matrix-vector multiplications

Oleg Verbitsky, Maksim Zhukovskii

We show that a canonical labeling of a random $n$ -vertex graph can be obtained by assigning to each vertex $x$ the triple $(w_{1} (x), w_{2} (x), w_{3} (x))$ , where $w_{k} (x)$ is the number of…

math.CO2023

Maximum chordal subgraphs of random graphs

Michael Krivelevich, Maksim Zhukovskii

We find asymptotics of the maximum size of a chordal subgraph in a binomial random graph $G (n, p)$ , for $p = const$ and $p = n^{- α + o (1)}$ .

math.CO2023

Reconstruction of graph colourings

Yury Demidovich, Yaroslav Panichkin, Maksim Zhukovskii

A $k$ -deck of a (coloured) graph is a multiset of its induced $k$ -vertex subgraphs. Given a graph $G$ , when is it possible to reconstruct with high probability a uniformly random c…

math.CO2023★ 1 cited

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes

Édouard Bonnet, Julien Duron, John Sylvester +2

We show that for any natural number $s$ , there is a constant $γ$ and a subgraph-closed class having, for any natural $n$ , at most $γ^{n}$ graphs on $n$ vertices up to isomorphism, bu…

math.CO2023

Maximum number of symmetric extensions in the random graph

Stepan Vakhrushev, Maksim Zhukovskii

It is known that after an appropriate rescaling the maximum degree of the binomial random graph converges in distribution to a Gumbel random variable. The same holds true for the m…

math.CO2023

Weak saturation in graphs: a combinatorial approach

Nikolai Terekhov, Maksim Zhukovskii

The weak saturation number $wsat (n, F)$ is the minimum number of edges in a graph on $n$ vertices such that all the missing edges can be activated sequentially so that each…

math.CO2023

Saturation numbers of bipartite graphs in random graphs

Meysam Miralaei, Ali Mohammadian, Behruz Tayfeh-Rezaie +1

For a given graph $F$ , the $F$ -saturation number of a graph $G$ , denoted by $s a t (G, F)$ , is the minimum number of edges in an edge-maximal $F$ -free subgraph of $G$ . In 2017, Kor…

math.CO2023

A Jump of the Saturation Number in Random Graphs?

Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii

For graphs $G$ and $F$ , the saturation number $sat (G, F)$ is the minimum number of edges in an inclusion-maximal $F$ -free subgraph of $G$ . In 2017, Korándi and Sudakov init…

math.CO2023

Sharp thresholds for spanning regular graphs

Maksim Zhukovskii

Let $d \geq 3$ be a constant and let $F$ be a $d$ -regular graph on $[n]$ with not too many symmetries. By the union bound, the probability threshold for the existence of a spanning…