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)

The Oxford Discrete Mathematics and Probability Seminar runs online. All welcome! On June 8, there will be a special Round the World Relay in Combinatorics, with 22 seminars from around the world.

I run an annual One-Day Meeting in Combinatorics in Oxford every May.
Last year's meeting was on
**Wednesday 29 May 2019**. There will be no meeting this year; however, next year's meeting is planned for **Wednesday 26 May 2021**.
Details about previous meetings can be found here.

I also organize seminars for the Combinatorics Group. The current seminar programme can be found here. From time to time, there are additional special events. For example, in **July 2008 ** there was
joint
workshop with Princeton. In **November 2009** there was a
Joint Seminar Afternoon with Warwick.
In **June/July 2010** there was
a series of lectures on Structural Graph Theory given by Paul Seymour and
Maria Chudnovsky, in **November 2010** there was a joint meeting on
Combinatorics and Quantum Gravity with
Theoretical Physics, and in **October 2011**
Geoff Whittle gave
two LMS Aitken Lectures on matroid theory.

*Submitted or accepted*

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

155. Active clustering for labeling training data,
*NeurIPS 2021, to appear* (with Quentin Lutz, Élie de Panafieu, and Maya Stein)

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

153. Polynomial bounds for chromatic number.
III. Excluding a double star,
*submitted* (with Paul Seymour and Sophie Spirkl)

152. Polynomial bounds for chromatic number.
II. Excluding a star-forest,
*submitted* (with Paul Seymour and Sophie Spirkl)

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

150. Counting partitions of G_{n,1/2} with degree congruence conditions,
*submitted* (with Paul Balister, Emil Powierski and Jane Tan)

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

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

147. Polynomial bounds for chromatic number.
I. Excluding a biclique and an induced tree,
*submitted* (with Paul Seymour and Sophie Spirkl)

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

145. 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)

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

143. A note on infinite antichain density,
*submitted* (with Paul Balister, Emil Powierski and Jane Tan)

142. 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)

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

140. Clustered colouring of graph classes with bounded treedepth or pathwidth,
*submitted* (with Sergey Norin and David Wood)

139. A note on simplicial cliques,
*Discrete Mathematics, to appear* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

138. Optimal labelling schemes for adjacency, comparability and reachability, *STOC 2021, to appear* (with Marthe Bonamy, Louis Esperet and Carla Groenland)

137. Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces,
*Journal of the European Mathematical Society, to appear* (with Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu and François Pirot)

136. Powers of paths in tournaments
*Combinatorics, Probability and Computing, to appear* (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)

135. Pure pairs. VI. Excluding an ordered tree,
*SIAM Journal on Discrete Mathematics, to appear* (with Paul Seymour and Sophie Spirkl)

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

133. Exact stability for Turán's Theorem,
*Advances in Combinatorics, to appear* (with Dániel Korándi and Alexander Roberts)

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

131. A universal exponent for homeomorphs,
*Israel J Math, to appear* (with Peter Keevash, Jason Long and Bhargav Narayanan)

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

129. Parking on the integers,
*submitted* (with Michał Przykucki and Alexander Roberts)

128. Shotgun reconstruction in the hypercube,
*Random Structures and Algorithms*
**60** (2022), 117-150
(with Michał Przykucki and Alexander Roberts)

127. 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)

126. Detecting a long odd hole,
*Combinatorica, to appear* (with Maria Chudnovsky and Paul Seymour)

125. 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)

124. Concatenating bipartite graphs,
*submitted* (with Maria Chudnovsky, Patrick Hompe, Paul Seymour and Sophie Spirkl)

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

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

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

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

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

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

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

116. 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)

115. Structure of random *r*-SAT below the pure literal threshold,*
submitted *(with Gregory Sorkin)

*Published papers, grouped by year*

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*

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