School of Mathematics
,
Birmingham University
Deryk Osthus
Publications
Preprints submitted:
Perfect matchings in random sparsifications of Dirac hypergraphs
(with Dong-Yeap Kang,
Tom Kelly
,
Daniela Kühn
and
Vincent Pfenninger
)
Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree
(with Dong-Yeap Kang,
Tom Kelly
,
Daniela Kühn
and
Abhishek Methuku
)
A special case of Vu's conjecture: Coloring nearly disjoint graphs of bounded maximum degree
(with
Tom Kelly
and
Daniela Kühn
)
New bounds on the size of nearly perfect matchings in almost regular hypergraphs
(with Dong-Yeap Kang,
Daniela Kühn
and
Abhishek Methuku
)
A characterization of testable hypergraph properties
(with
Felix Joos
,
Jaehoon Kim
, and
Daniela Kühn
).
An
extended abstract
of this paper appears at FOCS 2017.
Preprints accepted:
Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
(with Dong-Yeap Kang,
Tom Kelly
,
Daniela Kühn
and
Abhishek Methuku
, Transactions AMS, to appear)
A proof of the Erdős-Faber-Lovász conjecture
(with Dong-Yeap Kang,
Tom Kelly
,
Daniela Kühn
and
Abhishek Methuku
, Annals of Mathematics, to appear)
An
extended abstract
of this paper appeared at FOCS 2021. Here is a
talk sketching the proof
.
Hamiltonicity of random subgraphs of the hypercube
(with
Padraig Condon
,
Alberto Espuny Díaz
,
Antonió Girão
and
Daniela Kühn
, Memoirs of the American Mathematical Society, to appear).
An
extended abstract
of this paper appears at SODA 2021.
Graph and hypergraph colouring via nibble methods: a survey
(with Dong-Yeap Kang,
Tom Kelly
,
Daniela Kühn
and
Abhishek Methuku
Proceedings of the 8th European Congress of Mathematics, to appear)
Hypergraph regularity and random sampling
(with
Felix Joos
,
Jaehoon Kim
, and
Daniela Kühn
, Random Structures Algorithms, to appear).
Papers:
2023
The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F
(with
Stefan Glock
,
Daniela Kühn
and
Allan Lo
, Memoirs of the American Mathematical Society 284 (2023), monograph 1406)
A shorter version which proves the case when F is a clique (i.e. a proof for the existence of designs) can be found
here
. Here is a
talk sketching the proof
.
Path decompositions of tournaments
(with
Antonió Girão
,
Bertille Granet
,
Daniela Kühn
and
Allan Lo
, Proceedings London Mathematical Society, 126 (2023) 429-517)
2022
Almost all optimally coloured complete graphs contain a rainbow Hamilton path
(with Stephen Gould,
Tom Kelly
and
Daniela Kühn
, J. Combinatorial Theory Series B 156 (2022), 57-100)
2021
Resolution of the Oberwolfach problem
(with
Stefan Glock
,
Felix Joos
,
Jaehoon Kim
and
Daniela Kühn
, Journal of the European Mathematical Society 23 (2021), 2511–2547)
Extremal aspects of graph and hypergraph decomposition problems
(with
Stefan Glock
and
Daniela Kühn
, Surveys in Combinatorics, London Mathematical Society Lecture Note Series 470, Cambridge University Press (2021), 235-266)
Dirac's theorem for random regular graphs
(with
Padraig Condon
,
Alberto Espuny Díaz
,
Antonió Girão
and
Daniela Kühn
, Combinatorics, Probability, Computing 30 (2021), 17-36)
Counting Hamilton cycles in Dirac hypergraphs
(with
Stefan Glock
, Stephen Gould,
Felix Joos
, and
Daniela Kühn
, Combinatorics, Probability, Computing 30 (2021), 631-653)
Path and cycle decompositions of dense graphs
(with
Antonió Girão
,
Bertille Granet
and
Daniela Kühn
, J. London Mathematical Society 104 (2021), 1085-1134)
Decompositions into isomorphic rainbow spanning trees
(with
Stefan Glock
,
Daniela Kühn
and
Richard Montgomery
, J. Combinatorial Theory Series B 146 (2021), 439-484)
2020
Euler tours in hypergraphs
(with
Stefan Glock
,
Felix Joos
, and
Daniela Kühn
, Combinatorica 40 (2020), 679–690)
Minimalist designs
(with
Ben Barber
,
Stefan Glock
,
Daniela Kühn
Allan Lo
and
Richard Montgomery
, Random Structures and Algorithms 57 (2020) 47-63)
Rainbow structures in locally bounded colourings of graphs
(with
Jaehoon Kim
, and
Daniela Kühn
and
Andrey Kupavskii
, Random Structures and Algorithms 56 (2020) 1171-1204)
On a conjecture of Erdős on locally sparse Steiner triple systems
(with
Stefan Glock
,
Daniela Kühn
and
Allan Lo
, Combinatorica 40 (2020), 363-403)
2019
Optimal packings of bounded degree trees
(with
Felix Joos
,
Jaehoon Kim
, and
Daniela Kühn
, J. European Math. Soc. 21 (2019), 3573-3647)
Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
(with
Padraig Condon
,
Alberto Espuny Díaz
,
Jaehoon Kim
and
Daniela Kühn
, Electronic J. Combinatorics 26 (2019), P4.54)
Edge correlations in random regular hypergraphs and applications to subgraph testing
(with
Alberto Espuny Díaz
,
Felix Joos
and
Daniela Kühn
, SIAM Journal Discrete Mathematics 33 (2019), 1837-1863)
On the decomposition threshold of a given graph
(with
Stefan Glock
,
Daniela Kühn
,
Allan Lo
and
Richard Montgomery
, J. Combinatorial Theory Series B 139 (2019), 47-127) Slides can be found
here
.
A bandwidth theorem for approximate decompositions
(with
Padraig Condon
,
Jaehoon Kim
and
Daniela Kühn
, Proceedings London Mathematical Society 118 (2019), 1393-1449)
A blow-up lemma for approximate decompositions
(with
Jaehoon Kim
,
Daniela Kühn
and Mykhaylo Tyomkyn, Transactions AMS 371 (2019), 4655-4742) Slides can be found
here
.
2018
Forbidding induced even cycles in a graph: typical structure and counting
(with
Jaehoon Kim
,
Daniela Kühn
and Timothy Townsend, J. Combinatorial Theory Series B 131 (2018), 170-219)
2017
Fractional clique decompositions of dense graphs and hypergraphs
(with
Ben Barber
,
Daniela Kühn
,
Allan Lo
and
Richard Montgomery
, J. Combinatorial Theory Series B 127 (2017) 148–186)
Clique decompositions of multipartite graphs and completion of Latin squares
(with
Ben Barber
,
Allan Lo
,
Deryk Osthus
and Amelia Taylor, J. Combinatorial Theory Series A 151 (2017), 146–201)
On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
(with
Daniela Kühn
, Timothy Townsend and
Yi Zhao
J. Combinatorial Theory B, 124 (2017), 88–127) Slides can be found
here
.
2016
Solution to a problem of Bollobas and Häggkvist on Hamilton cycles in regular graphs
(with
Daniela Kühn
,
Allan Lo
and
Katherine Staden
), J. Combinatorial Theory B, 121 (2016), 85-145).
Proof of the 1-factorization and Hamilton decomposition conjectures
(with
Bela Csaba
,
Daniela Kühn
,
Allan Lo
and
Andrew Treglown
, Memoirs of the American Mathematical Society, 244 (2016), monograph 1154, 170 pages)
Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
(with
Daniela Kühn
and Tim Townsend, Combinatorica, 36 (2016), 451–469)
On the random greedy F-free hypergraph process
(with
Daniela Kühn
and Amelia Taylor, SIAM Journal Discrete Mathematics, 30 (2016), 1343-1350)
Bipartitions of highly connected tournaments
(with
Jaehoon Kim
and
Daniela Kühn
, SIAM Journal Discrete Mathematics, 30 (2016), 895-911)
A domination algorithm for {0,1}-instances of the travelling salesman problem
(with
Daniela Kühn
and
Viresh Patel
, Random Structures and Algorithms, 48 (2016), 427–453)
Optimal path and cycle decompositions of dense quasirandom graphs
(with
Stefan Glock
and
Daniela Kühn
, J. Combinatorial Theory B 118 (2016), 88-108)
Edge-decompositions of graphs with high minimum degree
(with
Ben Barber
,
Daniela Kühn
and
Allan Lo
, Advances in Mathematics 288 (2016), 337-385) Slides can be found
here
.
2015
Arbitrary orientations of Hamilton cycles in digraphs
(with
Louis DeBiasio
,
Daniela Kühn
Theodore Molla
, and Amelia Taylor, SIAM Journal Discrete Mathematics 29 (2015), 1553-1584)
Edge-disjoint Hamilton cycles in random graphs
(with
Fiachra Knox
and
Daniela Kühn
, Random Structures and Algorithms 46 (2015), 397-445)
The robust component structure of dense regular graphs and applications
(with
Daniela Kühn
,
Allan Lo
and
Katherine Staden
, Proceedings London Mathematical Society 110 (2015), 19-56)
2014
Hamilton cycles in graphs and hypergraphs: an extremal perspective
(with
Daniela Kühn
, Proceedings of the International Congress of Mathematicians 2014, Seoul, Korea, Vol 4, 381-406).
A slightly expanded version of this survey can be found
here
. Slides for the talk can be found
here
.
Optimal covers with Hamilton cycles in random graphs
(with
Dan Hefetz
,
Daniela Kühn
and John Lapinskas, Combinatorica 34 (2014), 573-596)
Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
(with
Daniela Kühn
, John Lapinskas and
Viresh Patel
, Proceedings London Mathematical Society 109 (2014), 733-762)
Decompositions of complete uniform hypergraphs into Hamilton Berge cycles
(with
Daniela Kühn
, J. Combinatorial Theory A 126 (2014), 128-135)
Fractional and integer matchings in uniform hypergraphs
(with
Daniela Kühn
and Tim Townsend, European J. Combinatorics 38 (2014), 83-96)
Hamilton decompositions of regular expanders: applications
(with
Daniela Kühn
, J. Combinatorial Theory B 104 (2014), 1-27)
2013
Approximate Hamilton decompositions of robustly expanding regular digraphs
(with
Katherine Staden
, SIAM Journal Discrete Mathematics 27 (2013), 1372-1409)
Optimal packings of Hamilton cycles in graphs of high minimum degree
(with
Daniela Kühn
and John Lapinskas, Combinatorics, Probability, Computing 22 (2013), 394-416)
Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments
(with
Daniela Kühn
, Advances in Mathematics 237 (2013), 62-146) Slides can be found
here
.
Matchings in 3-uniform hypergraphs
(with
Daniela Kühn
and
Andrew Treglown
, J. Combinatorial Theory Series B 103 (2013), 291-305 )
Embedding cycles of given length in oriented graphs
(with
Daniela Kühn
and Diana Piguet, European J. Combinatorics 34 (2013), 495-501)
2012
On Posa's conjecture for random graphs
(with
Daniela Kühn
, SIAM Journal Discrete Mathematics 26 (2012), 1440-1457)
Edge-disjoint Hamilton cycles in graphs
(with
Demetres Christofides
and
Daniela Kühn
, J. Combinatorial Theory Series B 102 (2012), 1035-1060)
Finding Hamilton cycles in robustly expanding digraphs
(with
Demetres Christofides,
Peter Keevash
and
Daniela Kühn
, Journal of Graph Algorithms and Applications 16 (2012), 337-360)
A survey on Hamilton cycles in directed graphs
(with
Daniela Kühn
, European J. Combinatorics 33 (2012), 750-766)
Approximate Hamilton decompositions of random graphs
(with
Fiachra Knox
and
Daniela Kühn
, Random Structures and Algorithms 40 (2012), 133-149)
2011
An approximate version of Sumner's universal tournament conjecture
(with
Daniela Kühn
and
Richard Mycroft
, J. Combinatorial Theory Series B 101 (2011), 415-447)
A proof of Sumner's universal tournament conjecture for large tournaments
(with
Daniela Kühn
and
Richard Mycroft
, Proceedings of the London Mathematical Society 102 (2011), 731-766)
Loose Hamilton cycles in hypergraphs
(with
Peter Keevash
,
Richard Mycroft
and
Daniela Kühn
, Discrete Mathematics 311 (2011), 544-559)
2010
A semi-exact degree condition for Hamilton cycles in digraphs
(with
Demetres Christofides,
Peter Keevash
and
Daniela Kühn
), SIAM Journal Discrete Mathematics 24 (2010), 709-756.
Hamilton l-cycles in uniform hypergraphs
(with
Richard Mycroft
and
Daniela Kühn
), J. Combinatorial Theory Series A 117 (2010), 910-927.
Hamilton decompositions of regular tournaments
(with
Daniela Kühn
and
Andrew Treglown
), Proceedings of the London Mathematical Society 101 (2010), 303-335.
Hamiltonian degree sequences in digraphs
(with
Daniela Kühn
and
Andrew Treglown
), J. Combinatorial Theory Series B 100 (2010), 367-380.
Cycles of given length in oriented graphs
(with Luke Kelly and
Daniela Kühn
), J. Combinatorial Theory Series B 100 (2010), 251-264.
2009
Minors in random regular graphs
(with
Nikolaos Fountoulakis
and
Daniela Kühn
), Random Structures and Algorithms 35 (2009), 444-463.
An Ore-type theorem for perfect packings in graphs
(with
Daniela Kühn
and
Andrew Treglown
), SIAM Journal Discrete Mathematics 23 (2009), 1335-1355.
Embedding large subgraphs into dense graphs
(with
Daniela Kühn
), Surveys in Combinatorics 2009 (editors S. Huczynka, J. Mitchell, C. Roney-Dougal), Cambridge University Press, 2009, 137-167.
Embeddings and Ramsey numbers of sparse k-uniform hypergraphs
(with
Oliver Cooley
,
Nikolaos Fountoulakis
and
Daniela Kühn
), Combinatorica 29 (2009), 263-297
The minimum degree threshold for perfect graph packings
(with
Daniela Kühn
), Combinatorica 29 (2009), 65-107
An exact minimum degree condition for Hamilton cycles in oriented graphs
(with
Peter Keevash
and
Daniela Kühn
), Journal of the London Mathematical Society 79 (2009), 144-166
2008
A Dirac type result on Hamilton cycles in oriented graphs
(with Luke Kelly and
Daniela Kühn
), Combinatorics, Probability and Computing 17 (2008), 689-709
k-ordered Hamilton cycles in digraphs
(with
Daniela Kühn
and Andrew Young), J. Combinatorial Theory Series B 98 (2008) 1165-1180
A simple solution to Ulam's liar game with one lie
(with Rachel Watkinson), Elemente der Mathematik 63 (2008), 97-101
The order of the largest complete minor in a random graph
, with
Nikolaos Fountoulakis
and
Daniela Kühn
), Random Structures and Algorithms 33 (2008), 127-141
Linkedness and ordered cycles in digraphs
(with
Daniela Kühn
), Combinatorics, Probability and Computing 17 (2008), 411-422.
3-uniform hypergraphs of bounded degree have linear Ramsey numbers
(with
Oliver Cooley
,
Nikolaos Fountoulakis
and
Daniela Kühn
), J. Combinatorial Theory Series B 98 (2008), 484-505
A note on complete subdivisions in digraphs of large outdegree
(with
Daniela Kühn
and Andrew Young), Journal of Graph theory 57 (2008), 1-6
2007
Perfect packings with complete graphs minus an edge
(with Oliver Cooley and
Daniela Kühn
), European J. Combinatorics 28 (2007), 2143-2155
Maximizing several cuts simultaneously
(with
Daniela Kühn
), Combinatorics, Probability and Computing 16 (2007), 277-283
2006
Loose Hamilton cycles in 3-uniform hypergraphs of large minimum degree
(with
Daniela Kühn
), J. Combinatorial Theory Series B 96 (2006), 767-821
Multicoloured Hamilton cycles and perfect matchings in pseudo-random graphs
(with
Daniela Kühn
), SIAM Journal Discrete Mathematics 20 (2006), 273-286
Critical chromatic number and the complexity of perfect packings in graphs
(with
Daniela Kühn
), 17th ACM-SIAM Symposium on Discrete Algorithms 2006 (SODA), 851-859
Improved bounds for topological cliques in graphs of large girth
(with
Daniela Kühn
), SIAM Journal Discrete Mathematics 20 (2006), 62-78
Extremal connectivity for topological cliques in bipartite graphs
(with
Daniela Kühn
), J. Combinatorial Theory Series B, 96 (2006), 73-99
Matchings in hypergraphs of large minimum degree
(with
Daniela Kühn
), Journal of Graph Theory 51 (2006), 269-280
2005
Large planar subgraphs in dense graphs
(with
Daniela Kühn
and
Anusch Taraz
), J. Combinatorial Theory Series B 95 (2005), 263-282
Spanning triangulations in graphs
(with
Daniela Kühn
), Journal of Graph Theory 49 (2005), 205-233
Packings in dense regular graphs
(with
Daniela Kühn
), Combinatorics, Probability and Computing 14 (2005) 325-337
4-cycles in graphs without a given even cycle
(with
Daniela Kühn
), Journal of Graph Theory 48 (2005) 147-156
Forcing unbalanced complete bipartite minors
(with
Daniela Kühn
), European Journal of Combinatorics 26 (2005) 75-81
2004
Complete minors in K
s,s
-free graphs
(with
Daniela Kühn
), Combinatorica 25 (2004) 49-61
Induced subdivisions in K
s,s
-free graphs of large average degree
(with
Daniela Kühn
), Combinatorica 24 (2004), 287-304
Every graph of sufficiently large average degree contains a C
4
-free graph of large average degree
(with
Daniela Kühn
), Combinatorica 24 (2004), 155-162.
Popularity based random graph models leading to a scale-free degree distribution
(with Gerry Buckley), Discrete Mathematics 282 (2004), 53-68.
Subdivisions of K
r+2
in graphs of average degree at least r+epsilon and large but constant girth
(with
Daniela Kühn
), Combinatorics, Probability and Computing 13 (2004), 361-371.
Large topological cliques in graphs without a 4-cycle
(with
Daniela Kühn
), Combinatorics, Probability and Computing 13 (2004), 93-102.
2003
For which densities are random triangle-free graphs almost surely bipartite?
(with
Hans Jürgen Prömel
and
Anusch Taraz
), Combinatorica 23 (2003), 105-150.
Partitions of graphs with high minimum degree or connectivity
(with
Daniela Kühn
), J. Combinatorial Theory Series B 88 (2003), 29-43.
On random planar graphs, the number of planar graphs and their triangulations
(with
Hans Jürgen Prömel
and
Anusch Taraz
), J. Combinatorial Theory, Series B 88 (2003), 119-143.
Minors in graphs of large girth
(with
Daniela Kühn
), Random Structures and Algorithms 22 (2003), 213-225.
2000 - 2002
Topological minors in graphs of large girth
(with
Daniela Kühn
), J. Combinatorial Theory Series B 86 (2002), 364-380.
Almost all graphs of high girth and suitable density have high chromatic number
(with
Hans Jürgen Prömel
and
Anusch Taraz
), Journal of Graph Theory, 37 (2001) 220-226.
Random maximal H-free graphs
(with
Anusch Taraz
), Random Structures and Algorithms, 18 (2001) 61-82.
The length of random subsets of Boolean lattices
(with
Yoshi Kohayakawa
and Bernd Kreuter) Random Structures and Algorithms, 16 (2000) 177-194.
Maximum antichains in random subsets of a finite set
Journal of Combinatorial Theory, Series A, 90 (2000) 336-346.