Margarita Akhmejanova

activity

20202025

collaborators

7 papers

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

On the upper tail of star counts in random graphs

Margarita Akhmejanova, Matas Šileikis

Let $X$ count the number of $r$ -stars in the random binomial graph $G (n, p)$ . We determine, for fixed $r$ and $ε > 0$ , the asymptotics of $\log \mathbb{P}(X \ge (…

math.CO2024

Bicrucial $k$ -power-free permutations

Margarita Akhmejanova, Aiya Kuchukova, Alexandr Valyuzhenich +1

In this work, we prove that for every $k \geq 3$ there exist arbitrarily long bicrucial $k$ -power-free permutations. We also show that for every $k \geq 3$ there exist right-crucial…

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

The maximum size of an induced forest in the binomial random graph

Margarita Akhmejanova, Vladislav Kozhevnikov

The celebrated Frieze's result about the independence number of $G (n, p)$ states that it is concentrated in an interval of size $o (1/ p)$ for all $C_{ε} / n < p = o (1)$ . We show…

math.CO2021

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…