Margarita Akhmejanova

activity

20202026

most citedWiener index and graphs, almost half of whose vertices satisfy Šoltés property

1 citations · 1 across the 6 of their papers we have counts for

collaborators

8 papers

math.CO2026

Two-point concentration for graph classes admitting sparse vertex deletion

Margarita Akhmejanova, Vladislav Kozhevnikov

For fixed $p \in (0, 1)$ , we prove that the maximum number of vertices in an induced subgraph of $G (n, p)$ from a given class is concentrated on two consecutive integers, unifying and…

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…

math.CO2020★ 1 cited

Wiener index and graphs, almost half of whose vertices satisfy Šoltés property

Margarita Akhmejanova, Konstantin Olmezov, Aleksei Volostnov +3

The Wiener index $W (G)$ of a connected graph $G$ is a sum of distances between all pairs of vertices of $G$ . In 1991, Šoltés formulated the problem of finding all graphs $G$ such t…