Professor of Mathematics, University of Oxford

Dominic Welsh Tutor in Mathematics, Merton College

Research interests: Combinatorics, probability, algorithms and related areas

Phone (Institute): 01865 615314

Phone (College): 01865 276331

Email: lastname at maths.ox.ac.uk

My CV (January 2021)

I organize the Oxford Combinatorics Seminar. With Christina Goldschmidt, I run the online
Oxford Discrete Mathematics and Probability Seminar. All welcome!

I also organize the annual One-Day Meeting in Combinatorics in Oxford every May or June.
This year's meeting was on
**Wednesday 1 June 2022** (details about previous meetings can be found here). In June 2021, I organized a special Round the World Relay in Combinatorics, with 22 seminars from around the world.

*submitted*

169. Perfect shuffing with fewer lazy transpositions,
*submitted* (with Carla Groenland, Tom Johnston and Jamie Racliffe)

168. Short reachability networks,
*submitted* (with Carla Groenland, Tom Johnston and Jamie Racliffe)

167. Alon–Seymour–Thomas revisited,
*submitted* (with Freddie Illingworth and David Wood)

166. Improved bounds for 1-independent percolation on ℤ^{n},
*submitted* (with Paul Balister, Tom Johnston and Michael Savery)

165. Balancing connected colourings of graphs,
*submitted* (with Freddie Illingworth, Emil Powierski and Youri Tamitegama)

164. Bipartite graphs with no K_{6} minor,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

163. Induced subgraphs of induced subgraphs of large
chromatic number,
*submitted* (with António Girão, Freddie Illingworth, Emil Powierski,
Michael Savery, Youri Tamitegama and Jane Tan)

162. Pure pairs. X. Tournaments and the strong Erdős-Hajnal property,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

161. Decomposing random permutations into
order-isomorphic subpermutations,
*submitted* (with Carla Groenland, Tom Johnston, Dániel Korándi,
Alexander Roberts and Jane Tan)

160. Polynomial bounds for chromatic number.
VII. Disjoint holes,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

159. Polynomial bounds for chromatic number.
VI. Adding a four-vertex path,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

158. Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph, *submitted* (with Paul Seymour)

157. Pure pairs. VIII. Excluding a sparse graph,
*submitted* (with Paul Seymour and Sophie Spirkl)

156. Pure pairs. IX. Transversal trees,
*submitted* (with Paul Seymour and Sophie Spirkl)

155. Polynomial bounds for chromatic number.
IV. A near-polynomial bound for excluding the five-vertex path,
*submitted* (with Paul Seymour and Sophie Spirkl)

154. Powers of paths and cycles in tournaments
*submitted* (with António Girão and Dániel Korándi)

153. Strengthening Rödl's theorem,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

152. Pure pairs. V. Excluding some long subdivision,
*submitted* (with Paul Seymour and Sophie Spirkl)

151. Reconstructing trees from small cards,
*submitted* (with Carla Groenland, Tom Johnston and Jane Tan)

150. Reconstructing the degree sequence of a sparse graph from a partial deck,
*submitted* (with Carla Groenland, Tom Johnston, Andrey Kupavskii, Kitty Meeks and Jane Tan)

149. Erdős-Hajnal for graphs with no 5-hole,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

148. Best-response dynamics, playing sequences, and convergence to equilibrium in random games,
*submitted* (with Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo, Bassel Tarbush and Samuel Wiese)

147. Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a
forbidden submatrix,
*submitted* (with Paul Seymour and Sophie Spirkl)

146. Pure pairs. IV. Trees in bipartite graphs,
*submitted* (with Paul Seymour and Sophie Spirkl)

145. A logarithmic bound for the chromatic number of the associahedron,
*submitted* (with Louigi Addario-Berry, Bruce Reed and David Wood)

144. Approximating the position of a hidden agent in a graph,
*submitted* (with Hannah Guggiari and Alex Roberts)

*to appear*

142. Graphs of large chromatic number,

141. Polynomial bounds for chromatic number. III. Excluding a double star,

140. Polynomial bounds for chromatic number. II. Excluding a star-forest,

139. Counting partitions of G

138. Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree,

137. Clustered colouring of graph classes with bounded treedepth or pathwidth,

136. Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces,

*published papers*

134. Pure pairs. VI. Excluding an ordered tree,

133. Shotgun reconstruction in the hypercube,

132. Concatenating bipartite graphs,

131. Active clustering for labeling training data,
*35th Conference on Neural Information Processing Systems (NeurIPS 2021)* (with Quentin Lutz, Élie de Panafieu, and Maya Stein)

130. A note on simplicial cliques,
*Discrete Mathematics* **344** (2021), Article 112470 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

129. Optimal labelling schemes for adjacency, comparability and reachability, *Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)*,1109-1117 (with Marthe Bonamy, Louis Esperet and Carla Groenland)

128. Powers of paths in tournaments
*Combinatorics, Probability and Computing* **30** (2021), 894-898 (with Nemanja Draganić, François Dross, Jacob Fox, António Girão, Frédéric Havet, Dániel Korándi, William Lochet, David Munhá Correia and Benny Sudakov)

127. Exact stability for Turán's Theorem,
*Advances in Combinatorics*, December 29, 2021 (with Dániel Korándi and Alexander Roberts)

126. Finding a shortest odd hole,
*ACM Transactions on Algorithms* **17** (2021) Article 13, 21 pages (with Maria Chudnovsky and Paul Seymour)

125. A universal exponent for homeomorphs,
*Israel J. Math.* **243** (2021) 141-154 (with Peter Keevash, Jason Long and Bhargav Narayanan)

124. Monochromatic components in edge-coloured graphs with large minimum degree,
*Electronic Journal of Combinatorics* **28** (2021), P1.10 (with Hannah Guggiari)

123. Combinatorics in the exterior algebra and the Bollobás Two Families Theorem,
*Journal of the London Mathematical Society*
**104** (2021), 1812-1839
(with Elizabeth Wilmer)

122. Detecting a long odd hole,
*Combinatorica* **41** (2021), 1-30 (with Maria Chudnovsky and Paul Seymour)

121. Maximising the number of cycles in graphs with
forbidden subgraphs, *Journal of Combinatorial Theory, Series B* **147** (2021), 201-237 (with Natasha Morrison and Alex Roberts)

120. Lipschitz bijections between boolean functions,
*Combinatorics, Probability and Computing* **30** (2021) 513-525 (with Tom Johnston)

119. Separation dimension and degree,
*Math. Proc. Camb. Phil. Soc.* **170** (2021), 549-558 (with David Wood)

118. Size reconstructibility of graphs,
*Journal of Graph Theory* **96** (2021), 326-337 (with Carla Groenland and Hannah Guggiari)

117. Pure pairs. II. Excluding all subdivisions of a graph,
*Combinatorica* **41** (2021), 379-405 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

116. The component structure of dense random
subgraphs of the hypercube, *Random Structures and Algorithms* **59** (2021), 3-24
(with Colin McDiarmid and Paul Withers)

115. Induced subgraphs of graphs with large chromatic
number. V. Chandeliers and strings,
*Journal of Combinatorial Theory, Series B* **150** (2021), 195-243 (with Maria Chudnovsky and Paul Seymour)

114. Proof of the Kalai-Meshulam Conjecture,
*Israel J Math* **238** (2020), 639-661 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

113. Induced subgraphs of graphs with large chromatic number.
XIII. New brooms,
*European Journal of Combinatorics* **84** (2020), 103024 (with Paul Seymour)

112. Pure pairs. I. Trees and linear anticomplete pairs,
*Advances in Mathematics* **375** (2 December 2020), 107396 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

111. Partitioning the vertices of a torus into isomorphic
subgraphs,
*Journal of Combinatorial Theory, Series A* **174** (2020), 105252 (with Marthe Bonamy and Natasha Morrison)

110. Induced subgraphs of graphs with large chromatic number.
VI. Banana trees,
*Journal of Combinatorial Theory, Series B* **145** (2020), 487-510 (with Paul Seymour)

109. A survey of χ-boundedness,
*Journal of Graph Theory* **95** (2020), 473-504 (with Paul Seymour)

108. Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs,
* Journal of Graph Theory* **95** (2020), 315-340 (with Maria Chudnovsky, Jacob Fox, Paul Seymour and Sophie Spirkl)

107. Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p),
*Transactions of the AMS*
**373** (2020), 5517–5585
(with Christina Goldschmidt and Simon Griffiths)

106. Exceptional graphs for the random walk,
*Annales de l’Institut Henri Poincaré*, **56** (2020), 2017-2027 (with Juhan Aru, Carla Groenland, Tom Johnston, Bhargav Narayanan and Alex Roberts)

105. Induced subgraphs of graphs with large chromatic number.
VII. Gyárfás' complementation conjecture,
*Journal of Combinatorial Theory, Series B* **142** (2020), 43-55 (with Paul Seymour)

104. Detecting an odd hole,
* Journal of the ACM* **67**, 1, Article 5 (January 2020), 12 pages (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

103. Better bounds for poset dimension and boxicity,
*Transactions of the AMS* **373** (2020), 2157-2172 (with David Wood)

102. Induced subgraphs of graphs with large chromatic number.
VIII. Long odd holes,
*Journal of Combinatorial Theory, Series B* **140** (2020), 84-97(with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

101. Near-domination in graphs,
*Journal of Combinatorial Theory, Series A* **165** (2019), 392-407 (with Bruce Reed and Paul Seymour)

100. Maximising H-colourings of graphs,
*Journal of Graph Theory* **92** (2019), 172-185 (with Hannah Guggiari)

99. Towards Erdős-Hajnal for graphs with no 5-hole,
*Combinatorica* **39** (2019), 983-991 (with Maria Chudnovsky, Jacob Fox, Paul Seymour and Sophie Spirkl)

98. Clustered colouring in minor-closed classes,
*Combinatorica* **39** (2019), 1387-1412 (with Sergey Norin, Paul Seymour and David Wood)

97. Bad news for chordal partitions,
*Journal of Graph Theory* **90** (2019), 5-12 (with Paul Seymour and David Wood)

96. Induced subgraphs of graphs with large chromatic number.
XII. Distant stars,
*Journal of Graph Theory* **92** (2019), 237-254 (with Maria Chudnovsky and Paul Seymour)

95. Induced subgraphs of graphs with large chromatic number.
XI. Orientations,
*European Journal of Combinatorics* **76** (2019), 53-61 (with Maria Chudnovsky and Paul Seymour)

94. Induced subgraphs of graphs with large chromatic number.
X. Holes with specific residue,
*Combinatorica* **39** (2019), 1105-1132 (with Paul Seymour)

93. Disjoint paths in unions of tournaments,
*Journal of Combinatorial Theory, Series B*
**135** (2019), 238-255
(with Maria Chudnovsky and Paul Seymour)

92. H-colouring P_{t}-free graphs in subexponential time,
*Discrete Applied Mathematics*
**92** (2019), 172-185
(with Carla Groenland, Karolina Okrasa, Paweł Rzążewski, Paul Seymour and Sophie Spirkl)

91. Stability results for graphs with a critical edge,
*European Journal of Combinatorics* **94** (2018), 27-38 (with Alexander Roberts)

90. Balancing sums of random vectors,
*Discrete Analysis* 2018:4, 16 pp. (with Juhan Aru, Bhargav Narayanan and Ramarathnam Venkatesan)

89. Induced subgraphs of graphs with large chromatic number. IV.
Consecutive holes,
*Journal of Combinatorial Theory, Series B* **132** (2018), 180-235 (with Paul Seymour)

88.
How unproportional must a graph be?,
*European Journal of Combinatorics* **73** (2018), 138-152 (with Humberto Naves and Oleg Pikhurko)

87. Supersaturation in posets and applications involving the container method,
*Journal of Combinatorial Theory, Series A* **154** (2018), 247-284
(with Jonathan Noel and Benny Sudakov)

86. Induced subgraphs of graphs with large chromatic number.
IX. Rainbow paths,
*Electronic Journal of Combinatorics*
**24** (2017), Paper P2.53
(with Paul Seymour)

85. Induced subgraphs of graphs with large chromatic
number. III. Long holes,
*Combinatorica*
**37** (2017), 1057-1072
(with Maria Chudnovsky and Paul Seymour)

84. A note on intersecting hypergraphs with large cover number,
*Electronic Journal of Combinatorics* **24** (2017), Paper P3.26 (with Penny Haxell)

83. Maximising the number of induced cycles in a graph,
*Journal of Combinatorial Theory, Series B*
**126** (2017), 24-61
(with Natasha Morrison)

82. On a problem of Erdős and Moser,
*Abhandlungen des Mathematischen Seminars der Universität Hamburg*
**87** (2017), 213-222
(with Béla Bollobás)

81. Packing random graphs and hypergraphs,
*Random Structures and Algorithms*
**51** (2017), 3-13
(with Béla Bollobás and Svante Janson)

80. Saturation in the hypercube and bootstrap percolation,
*Combinatorics, Probability and Computing* **26** (2017), 78-98 (with Natasha Morrison and Jonathan Noel)

79. On lower bounds for the matching number of subcubic graphs,
*Journal of Graph Theory*
**85** (2017), 336-348 (with Penny Haxell)

78. Uniform multicommodity flows in the hypercube with random edge capacities,
*Random Structures and Algorithms*,
**50** (2017), 437-463
(with Colin McDiarmid and Paul Withers)

77. Induced subgraphs of graphs with large chromatic number.
I. Odd holes,
*Journal of Combinatorial Theory, Series B* **121** (2016), 68-84 (with Paul Seymour)

76. Induced subgraphs of graphs with large chromatic number.
II. Three steps towards Gyárfás' conjectures,
*Journal of Combinatorial Theory, Series B* **118** (2016), 109–128
(with Maria Chudnovsky and Paul Seymour)

75. Random graphs from a block-stable class,
*European Journal of Combinatorics* **58** (2016), 96-106 (with Colin McDiarmid)

74. Disjoint dijoins,
*Journal of Combinatorial Theory Series B* **120** (2016), 18-35 (with Maria Chudnovsky, Katherine Edwards, Ringi Kim and Paul Seymour)

73. Feedback from nature: simple randomised distributed algorithms for
maximal independent set selection and greedy colouring,
*Distributed Computing* **29** (2016), 377-393
(with Peter Jeavons and Lei Xu; journal version of #62)

72. The parameterised complexity of
list problems on graphs of bounded treewidth, *Information and Computation*
**251** (2016), 91–103 (with Kitty Meeks)

71. Disjoint induced subgraphs of the same order and size,
*European Journal of Combinatorics* **49** (2015), 153-166
(with Béla Bollobás, Teeradej Kittipassorn and Bhargav Narayanan)

70. Disjoint paths in tournaments,
*Advances in Mathematics* **270** (2015), 582-597 (with Maria Chudnovsky and Paul Seymour)

69. Intersections of hypergraphs,
*Journal of Combinatorial Theory, Series B*** 110** (2015), 180–208 (with Béla Bollobás)

68. Intersections of random hypergraphs and
tournaments, *European Journal of Combinatorics* **44A** (2015), 125–139 (with Béla Bollobás)

67. Complete monotonicity for inverse powers
of some combinatorially defined polynomials, *Acta Mathematica* **213** (2014), 323-392 (with Alan Sokal)

66. Excluding pairs of graphs,
*Journal of Combinatorial Theory, Series B* **106** (2014), 15-29 (with Maria Chudnovsky and Paul Seymour)

65. On Saturated *k*-Sperner Systems,
*Electronic Journal of Combinatorics* **21** (2014), Paper #P3.22 (with Natasha Morrison and Jonathan Noel)

64. For most graphs H, most H-free graphs have
a linear homogeneous set, *Random Structures and Algorithms* **45** (2014), 343–361 (with Ross J. Kang, Colin
McDiarmid and Bruce Reed)

63. Hypergraphs of bounded disjointness,
*SIAM Journal on Discrete Mathematics*** 28** (2014), 372-384 (with Elizabeth Wilmer)

62.
Spanning trees and the complexity of flood-filling games
*Theory Comput. Syst.*** 54** (2014), 731-753;
preliminary version,
* FUN 2012, Lecture Notes in Computer Science*** 7288** (2012), 282-292;
(with Kitty Meeks)

61. Feedback from nature: an optimal distributed algorithm
for maximal independent set selection,
*PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing* (2013), 147-156 (with Peter Jeavons and Lei Xu)

60. Substitution and
χ-boundedness,
*Journal of Combinatorial Theory, Series B*** 103** (2013), 567-586 (with Maria Chudnovsky, Irena
Penev and Nicolas Trotignon)

59. Tournaments and colouring,
*Journal of Combinatorial Theory, Series B*** 103** (2013), 1-20 (with Eli Berger, Krzysztof Choromanski, Maria
Chudnovksy, Jacob Fox, Martin Loebl, Paul Seymour and Stephan Thomassé)

58. The complexity of Free-Flood-It on 2xn
boards, *Theoretical Computer Science*** 500** (2013), 25-43 (with Kitty Meeks)

57. A counterexample to a conjecture of
Schwartz, *Social Choice and Welfare*** 40** (2013), 739-743 (with Felix Brandt, Maria Chudnovsky, Ilhee Kim,
Gaku Liu, Sergey Norin, Paul Seymour and Stephan Thomassé)

56. Excluding induced subdivisions of the
bull and related graphs, *Journal of Graph Theory*** 71** (2012), 49-68 (with Maria Chudnovsky, Irena
Penev and Nicolas Trotignon)

55. Monochromatic cycles in 2-Coloured graphs,
*Combinatorics, Probability and Computing*** 21** (2012), 57-87 (with
Fabricio Benevides, Tomasz Łuczak, Jozef Skokan and Matthew White)

54. The complexity of flood-filling games on
graphs, *Discrete Applied Mathematics*** 160** (2012), 959-969 (with Kitty Meeks)

53. The minimal covering set in large
tournaments, *Social Choice and Welfare*** 38** (2012), 1-9 (with Mark Fey)

52. On Ryser's Conjecture, *Electronic
Journal of Combinatorics*** 19** (2012), #P23*,* 10 pages
(with Penny Haxell)

51.
A bound for the cops and robbers
problem, *SIAM Journal on Discrete Mathematics*** 25** (2011), 1438-1442 (with Benny Sudakov)

50. Cover-decomposition and polychromatic
numbers
*SIAM Journal of Discrete Mathematics*** 27** (2013), 240-256;
preliminary version,* Algorithms – ESA 2011, Lecture Notes in Computer Science* ** 6942** (2011),
799-810 (with Béla Bollobás,
David Pritchard and Thomas Rothvoss)

49. Szemerédi's Regularity Lemma for matrices and sparse graphs,
*Combinatorics, Probability and Computing* **20 **(2011), 455-466

48. Intersections of graphs, *Journal
of Graph
Theory*** 66 **(2011)

47. Almost all

46. Max

45. Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model),

44. Uniform multicommodity flow through the complete graph with random edge-capacities,

43. Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function,

42. Maximum directed cuts in acyclic digraphs,

41. Linear-programming design and analysis of fast algorithms for Max 2-CSP,

40. On separating systems,

39. Computational complexity of some restricted instances of 3SAT,

38. Separating systems and oriented graphs of diameter two,

37. Partitions and orientations of the Rado graph,

36. Infinite locally random graphs,

35. On dependency graphs and the lattice gas,

34. An LP-Designed Algorithm for Constraint Satisfaction,

33. Reconstructing under group actions,

32. Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time,

31. Discrepancy in graphs and hypergraphs,

30. The repulsive lattice gas, the independent-set polynomial, and the Lovász Local Lemma,

29. Judicious partitions and related problems, in

28. Reversals and transpositions over finite alphabets,

27. Max Cut for random graphs with a planted partition,

26. Judicious partitions of bounded-degree graphs,

25. Finite subsets of the plane are 18-reconstructible,

24. Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances,

23. Problems and results on judicious partitions,

22. On cycle lengths in graphs,

21. Better bounds for Max Cut,

20. Alternating knot diagrams, Euler circuits and the interlace polynomial,

19. On induced subgraphs with all degrees odd,

18. Subdivisions of transitive tournaments,

17. Judicious partitions of 3-uniform hypergraphs,

16. Exact bounds for judicious bipartitions of graphs,

15. Another simple proof of a theorem of Milner,

14. Reconstructing subsets of reals,

13. Induced cycles and chromatic number,

12. Reconstructing subsets of Z

11. Judicious partitions of hypergraphs,

10. Induced trees in graphs of large chromatic number,

9. Reconstructing sequences,

8. All trees contain a large induced subgraph having all degrees 1 (mod k),

7. On graph decompositions modulo k,

6. Better bounds for perpetual gossiping,

5. Independent sets and repeated degrees,

4. A proof of a conjecture of Bondy concerning paths in weighted digraphs,

3. Every tree has a large induced subgraph with all degrees odd

2. On judicious partitions of graphs,

1. Large induced subgraphs with all degrees odd,

*Edited book*

*Other publications*

3. The paradox of the question,

2. Taking the Measure of Doom,

1. What is in the Two Envelopes Paradox?,

*Technical reports*

9. Structure of random *r*-SAT below the pure literal threshold,
CoRR abs/1008.1260 (2010) (with Gregory Sorkin)

8. Generalized Constraint Satisfaction
Problems, IBM Technical Report RC23935 (2006) (with Gregory
Sorkin)

7. Computational Complexity of Some Restricted Instances of 3SAT,
Electronic Colloquium on Computational Complexity, Technical Report TR04-111
(with Piotr Berman and Marek Karpinski)

6. Faster exponential algorithms for Max Cut, Max 2-Sat and Max k-Cut,
IBM Technical Report RC23457 (2004) (with Gregory Sorkin)

5. Solving sparse semi-random instances of Max Cut and Max 2-CSP, IBM
Technical report RC23417 (2004) (with Gregory Sorkin)

4. Approximation hardness and satisfiability of bounded occurrence
instances of SAT, Electronic Colloquium on Computational Complexity, Technical
Report TR03-022 (2003) (with Piotr Berman and Marek Karpinski)

3. Approximation hardness of short symmetric instances of MAX-3SAT,
Electronic Colloquium on Computational Complexity, Technical Report TR03-049 (2003)
(with Piotr Berman and Marek Karpinski)

2. Arithmetic progressions of cycles, Technical Report No. 16 (1998),
Matematiska Institutionen, Umea universitet (with Roland Haggkvist)

1. Cycles of nearly equal length in cubic graphs, Technical Report No.
15 (1998), Matematiska Institutionen, Umea universitet (with Roland Haggkvist)

Katherine and Nick