M. Zhukovskii

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)}$ .

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…

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…

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…

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…

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…

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…

Tight concentration of star saturation number in random graphs

Sergej Demyanov, Maksim Zhukovskii

For given graphs $F$ and $G$ , the minimum number of edges in an inclusion-maximal $F$ -free subgraph of $G$ is called the $F$ -saturation number and denoted $sat (G, F)$ . For…

math.CO2022

On vertex Ramsey graphs with forbidden subgraphs

Sahar Diskin, Ilay Hoshen, Michael Krivelevich +1

A classical vertex Ramsey result due to Nešetřil and Rödl states that given a finite family of graphs $F$ , a graph $A$ and a positive integer $r$ , if every graph $B\in\ma…

Randomly twisted hypercubes -- between structure and randomness

Itai Benjamini, Yotam Dikstein, Renan Gross +1

Twisted hypercubes are generalizations of the Boolean hypercube, obtained by iteratively connecting two instances of a graph by a uniformly random perfect matching. Dudek et al. sh…

A very sharp threshold for first order logic distinguishability of random graphs

Itai Benjamini, Maksim Zhukovskii

In this paper we find an integer $h = h (n)$ such that the minimum number of variables of a first order sentence that distinguishes between two independent uniformly distributed rando…

Global information from local observations of the noisy voter model on a graph

Itai Benjamini, Hagai Helman Tov, Maksim Zhukovskii

We observe the outcome of the discrete time noisy voter model at a single vertex of a graph. We show that certain pairs of graphs can be distinguished by the frequency of repetitio…

Large cycles in generalized Johnson graphs

Vladislav Kozhevnikov, Maksim Zhukovskii

We count cycles of an unbounded length in generalized Johnson graphs. Asymptotics of the number of such cycles is obtained for certain growth rates of the cycle length.

Covering three-tori with cubes

Ilya Bogdanov, Oleg Grigoryan, Maksim Zhukovskii

Let $μ (ε)$ be the minimum number of cubes of side $ε$ needed to cover the unit three-torus $[R / Z]^{3}$ . We prove new lower and upper bounds for…

Spectrum of FO logic with quantifier depth 4 is finite

Yury Yarovikov, Maksim Zhukovskii

The $k$ -spectrum is the set of all $α > 0$ such that $G (n, n^{- α})$ does not obey the 0-1 law for FO sentences with quantifier depth at most $k$ . In this paper, we prove that the mini…

Cycle saturation in random graphs

Yury Demidovich, Arkadiy Skorkin, Maksim Zhukovskii

For a fixed graph $F,$ the minimum number of edges in an edge-maximal $F$ -free subgraph of $G$ is called the $F$ -saturation number. The asymptotics of the $F$ -saturation number of…

Weak saturation stability

Olga Kalinichenko, Maksim Zhukovskii

The paper studies wsat $(G, H)$ which is the minimum number of edges in a weakly $H$ -saturated subgraph of $G$ . We prove that wsat $(K_{n}, H)$ is `stable' - remains the same after indep…

EMSO(FO $^{2}$ ) 0-1 law fails for all dense random graphs

Margarita Akhmejanova, Maksim Zhukovskii

In this paper, we disprove EMSO(FO $^{2}$ ) convergence law for the binomial random graph $G (n, p)$ for any constant probability $p$ . More specifically, we prove that there exists an ex…