Alexey Pokrovskiy

collaborators

7 papers

math.CO2025

Embedding trees using minimum and maximum degree conditions

Alexey Pokrovskiy, Leo Versteegen, Ella Williams

A variant of the Erdős-Sós conjecture, posed by Havet, Reed, Stein and Wood, states that every graph with minimum degree at least $⌊ 2 k /3 ⌋$ and maximum degree at least…

math.CO2025

On the gracesize of trees

Shoham Letzter, Alexey Pokrovskiy, Ella Williams

An $n$ -vertex tree $T$ is said to be $graceful$ if there exists a bijective labelling $ϕ : V (T) \to {1, \dots, n}$ such that the edge-differences $\{|ϕ(x)-ϕ(y)| : xy\in E(T)…

math.CO2025

On the Graham--Sloane harmonious labelling conjecture

Alp Müyesser, Alexey Pokrovskiy

Consider an order $n$ abelian group $G$ and a tree $T$ on $n$ vertices. When is it possible to (bijectively) label $V (T)$ by $G$ so that along all edges $x y$ of $T$ , the sums $x + y$ …

math.CO2025

On Independent Spanning Trees in Random and Pseudorandom Graphs

Nemanja Draganić, Keith Frankston, Michael Krivelevich +2

In 1989, Zehavi and Itai conjectured that every $k$ -connected graph contains $k$ independent spanning trees rooted at any prescribed vertex $r$ . That is, for each vertex $v$ , the u…

math.CO2024

Hyperstability in the Erdős-Sós Conjecture

Alexey Pokrovskiy

A rough structure theorem is proved for graphs $G$ containing no copy of a bounded degree tree $T$ : from any such $G$ , one can delete $o (∣ G ∣∣ T ∣)$ edges in order to get a subgraph a…

math.CO2024

Notes on embedding trees in graphs with O(|T|)-sized covers

Alexey Pokrovskiy

This is a companion paper to the paper "Hyperstability in the Erdos-Sos Conjecture". In that paper the following rough structure theorem was proved for graphs G containing no copy…