A. Pokrovskiy

activity

20102026

most citedDecompositions into spanning rainbow structures

32 citations · 98 across the 35 of their papers we have counts for

collaborators

56 papers

math.CO2026

Minimising the harmonic sum of cycle lengths

Richard Montgomery, Aleksa Milojević, Alexey Pokrovskiy +1

A central theme in extremal graph theory is to understand the relationship between the density of a graph and the richness of its cycle length spectrum, which is the set of distinc…

math.CO2026

A proof of Andersen's rainbow path conjecture for large $n$

Candida Bowtell, Richard Montgomery, Alp Müyesser +1

We show that, for sufficiently large $n$ , every properly edge-coloured $n$ -vertex complete graph contains a path with $n - 1$ vertices which uses each colour at most once (that is, a…

math.CO2026

Nearly-uniform degree distributions in spanning subgraphs

Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov

We show that, when $d = o (n)$ , every $d$ -regular $n$ -vertex graph contains a spanning subgraph whose degree distribution is nearly uniform, i.e., for each $0 \leq i \leq d$ , there are…

math.CO2025

Size-Ramsey numbers of tight paths

Shoham Letzter, Alexey Pokrovskiy, Liana Yepremyan

The $s$ -colour size-Ramsey number of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$ whose every $s$ -edge-colouring contains a monochromatic copy of $H$ . We sho…

math.CO2025

Towards Graham's rearrangement conjecture via rainbow paths

Matija Bucić, Bryce Frederickson, Alp Müyesser +2

We study an old question in combinatorial group theory which can be traced back to a conjecture of Graham from 1971. Given a group $Γ$ , and some subset $S \subseteq Γ$ , is it possib…

math.CO2024★ 1 cited

Approximate path decompositions of regular graphs

Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy +1

We show that the edges of any $d$ -regular graph can be almost decomposed into paths of length roughly $d$ , giving an approximate solution to a problem of Kotzig from 1957. Along th…

math.CO2024★ 1 cited

Hamiltonicity of expanders: optimal bounds and applications

Nemanja Draganić, Richard Montgomery, David Munhá Correia +2

An $n$ -vertex graph $G$ is a $C$ -expander if $∣ N (X) ∣ \geq C ∣ X ∣$ for every $X \subseteq V (G)$ with $∣ X ∣ < n /2 C$ and there is an edge between every two disjoint sets of at least $n /2 C$ …

math.CO2023

Ascending Subgraph Decomposition

Kyriakos Katsamaktsis, Shoham Letzter, Alexey Pokrovskiy +1

A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph $G$ into copies $H_{1}, \dots, H_{m}$ are also suf…

math.CO2023

Optimal spread for spanning subgraphs of Dirac hypergraphs

Tom Kelly, Alp Müyesser, Alexey Pokrovskiy

Let $G$ and $H$ be hypergraphs on $n$ vertices, and suppose $H$ has large enough minimum degree to necessarily contain a copy of $G$ as a subgraph. We give a general method to rand…

math.CO2022★ 1 cited

Decomposing cubic graphs into isomorphic linear forests

Gal Kronenberg, Shoham Letzter, Alexey Pokrovskiy +1

A common problem in graph colouring seeks to decompose the edge set of a given graph into few similar and simple subgraphs, under certain divisibility conditions. In 1987 Wormald c…

math.CO2022★ 2 cited

The Turán density of tight cycles in three-uniform hypergraphs

Nina Kamčev, Shoham Letzter, Alexey Pokrovskiy

The Turán density of an $r$ -uniform hypergraph $H$ , denoted $π (H)$ , is the limit of the maximum density of an $n$ -vertex $r$ -uniform hypergraph not containing a…

math.CO2022

Chi-boundedness of graphs containing no cycles with $k$ chords

Joonkyung Lee, Shoham Letzter, Alexey Pokrovskiy

We prove that the family of graphs containing no cycle with exactly $k$ -chords is $χ$ -bounded, for $k$ large enough or of form $ℓ (ℓ - 2)$ with $ℓ \geq 3$ an integer. This ver…

math.CO2022

Graphs with Sudoku number $n - 1$

Alexey Pokrovskiy

Recently Lau-Jeyaseeli-Shiu-Arumugam introduced the concept of the "Sudoku colourings" of graphs -- partial $χ (G)$ -colourings of $G$ that have a unique extension to a proper $χ (G)$ …

math.CO2022★ 1 cited

A random Hall-Paige conjecture

Alp Müyesser, Alexey Pokrovskiy

A complete mapping of a group $G$ is a bijection $ϕ : G \to G$ such that $x \mapsto x ϕ (x)$ is also bijective. Hall and Paige conjectured in 1955 that a finite group $G$ has a com…

math.CO2021★ 1 cited

Short proofs of rainbow matching results

David Munhá Correia, Alexey Pokrovskiy, Benny Sudakov

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares and ha…

math.CO2021★ 4 cited

Size-Ramsey numbers of powers of hypergraph trees and long subdivisions

Shoham Letzter, Alexey Pokrovskiy, Liana Yepremyan

The $s$ -colour size-Ramsey number of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$ whose every $s$ -edge-colouring contains a monochromatic copy of $H$ . We sho…

math.CO2020

Isomorphic Bisections of Cubic Graphs

Shagnik Das, Alexey Pokrovskiy, Benny Sudakov

Graph partitioning, or the dividing of a graph into two or more parts based on certain conditions, arises naturally throughout discrete mathematics, and problems of this kind have…

math.CO2020★ 2 cited

Rota's Basis Conjecture holds asymptotically

Alexey Pokrovskiy

Rota's Basis Conjecture is a well known problem from matroid theory, that states that for any collection of $n$ bases in a rank $n$ matroid, it is possible to decompose all the ele…

math.CO2020★ 1 cited

New bounds for Ryser's conjecture and related problems

Peter Keevash, Alexey Pokrovskiy, Benny Sudakov +1

A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cel…

math.CO2020

C4-free subgraphs with large average degree

Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov

Motivated by a longstanding conjecture of Thomassen, we study how large the average degree of a graph needs to be to imply that it contains a $C_{4}$ -free subgraph with average degre…

math.CO2020

A proof of Ringel's Conjecture

Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov

A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$ . One of the oldest and best known conjectures…

math.CO2019

The maximum length of $K_{r}$ -Bootstrap Percolation

József Balogh, Gal Kronenberg, Alexey Pokrovskiy +1

Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges $E_{0}$ , and we infect…

math.CO2019

On the Odd Cycle Game and Connected Rules

Jan Corsten, Adva Mond, Alexey Pokrovskiy +2

We study the positional game where two players, Maker and Breaker, alternately select respectively $1$ and $b$ previously unclaimed edges of $K_{n}$ . Maker wins if she succeeds in cl…

math.CO2019

2-factors with k cycles in Hamiltonian graphs

Matija Bucić, Erik Jahn, Alexey Pokrovskiy +1

A well known generalisation of Dirac's theorem states that if a graph $G$ on $n \geq 4 k$ vertices has minimum degree at least $n /2$ then $G$ contains a $2$ -factor consisting of exact…

Minimising the harmonic sum of cycle lengths

A proof of Andersen's rainbow path conjecture for large n

Nearly-uniform degree distributions in spanning subgraphs

Size-Ramsey numbers of tight paths

Towards Graham's rearrangement conjecture via rainbow paths

Approximate path decompositions of regular graphs

Hamiltonicity of expanders: optimal bounds and applications

Ascending Subgraph Decomposition

Optimal spread for spanning subgraphs of Dirac hypergraphs

Decomposing cubic graphs into isomorphic linear forests

The Turán density of tight cycles in three-uniform hypergraphs

Chi-boundedness of graphs containing no cycles with k chords

Graphs with Sudoku number n−1

A random Hall-Paige conjecture

Short proofs of rainbow matching results

Size-Ramsey numbers of powers of hypergraph trees and long subdivisions

Isomorphic Bisections of Cubic Graphs

Rota's Basis Conjecture holds asymptotically

New bounds for Ryser's conjecture and related problems

C4-free subgraphs with large average degree

A proof of Ringel's Conjecture

The maximum length of Kr​-Bootstrap Percolation

On the Odd Cycle Game and Connected Rules

2-factors with k cycles in Hamiltonian graphs

A proof of Andersen's rainbow path conjecture for large $n$

Chi-boundedness of graphs containing no cycles with $k$ chords

Graphs with Sudoku number $n - 1$

The maximum length of $K_{r}$ -Bootstrap Percolation