1 citations · 2 across the 11 of their papers we have counts for
11 papers · 1 filter
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…
A proof of Andersen's rainbow path conjecture for large
Candida Bowtell, Richard Montgomery, Alp Müyesser +1
We show that, for sufficiently large , every properly edge-coloured -vertex complete graph contains a path with vertices which uses each colour at most once (that is, a…
Recent progress in graph theory using expansion
Richard Montgomery
Graph expansion has long been recognised as an important and desirable property with applications in a wide range of areas in computer science and mathematics. A particular form of…
Nearly-uniform degree distributions in spanning subgraphs
Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov
We show that, when , every -regular -vertex graph contains a spanning subgraph whose degree distribution is nearly uniform, i.e., for each , there are…
Packing subdivisions into regular graphs
Richard Montgomery, Kalina Petrova, Arjun Ranganathan +1
We show that, for any graph and , there exists a such that every -vertex -regular graph with has a collection of vertex-disjoint -subd…
On decomposition thresholds for odd-length cycles and other tripartite graphs
Darryn Bryant, Peter Dukes, Daniel Horsley +2
An (edge) decomposition of a graph is a set of subgraphs of whose edge sets partition the edge set of . Here we show, for each odd , that any graph of s…
Regular subgraphs at every density
Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1
In 1975, Erdős and Sauer asked to estimate, for any constant , the maximum number of edges an -vertex graph can have without containing an -regular subgraph. In a recent b…
Approximate path decompositions of regular graphs
Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy +1
We show that the edges of any -regular graph can be almost decomposed into paths of length roughly , giving an approximate solution to a problem of Kotzig from 1957. Along th…
Edge-disjoint cycles with the same vertex set
Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1
In 1975, Erdős asked for the maximum number of edges that an -vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turá…
Hamiltonicity of expanders: optimal bounds and applications
Nemanja Draganić, Richard Montgomery, David Munhá Correia +2
An -vertex graph is a -expander if for every with and there is an edge between every two disjoint sets of at least …
Spanning trees in dense directed graphs
Amarja Kathapurkar, Richard Montgomery
In 2001, Komlós, Sárközy and Szemerédi proved that, for each , there is some and such that, if , then every -vertex graph with minimum degree at leas…