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 will take place on
**Tuesday 21 May 2024** (please note that this is different from the usual day; details about previous meetings can be found here). The meeting has been running since 1999, with a brief interruption for covid (in June 2021, I organized a special Round the World Relay in Combinatorics, with 22 seminars from around the world).

*submitted*

200. Lower bounds for graph reconstruction with maximal independent set queries, *submitted* (with Lukas Michel)

199. A note on graphs of k-colourings, *submitted* (with Emma Hogan, Youri Tamitegama and Jane Tan)

198. Non-homotopic drawings of multigraphs, *submitted* (with António Girão, Freddie Illingworth and David Wood)

197. A counterexample to the coarse Menger conjecture, *submitted* (with Tung Nguyen and Paul Seymour)

196. Reconstruction of shredded random matrices, *submitted* (with Paul Balister, Gal Kronenberg and Youri Tamitegama)

195. Induced subgraph density. VII. The five-vertex path, *submitted* (with Tung Nguyen and Paul Seymour)

194. Induced subgraph density. VI. Bounded VC-dimension , *submitted* (with Tung Nguyen and Paul Seymour)

193. Graphs with arbitrary Ramsey number and connectivity, *submitted* (with Isabel Ahme)

192. Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut, *submitted* (with Lukas Michel)

191. Game connectivity and adaptive dynamics, *submitted* (with Tom Johnston, Michael Savery and Bassel Tarbush)

190. Boundary rigidity of 3D CAT(0) cube complexes, *submitted* (with John Haslegrave, Youri Tamitegama and Jane Tan)

189. Induced subgraph density. V. All paths approach Erdős-Hajnal, *submitted* (with Tung Nguyen and Paul Seymour)

188. Induced subgraph density. IV. New graphs with the Erdős-Hajnal property, *submitted* (with Tung Nguyen and Paul Seymour)

187. Induced C_{4}-free subgraphs with large average degree,
*submitted* (with Xiying Du, António Girão, Zach Hunter and Rose McCarty)

186. Induced subgraph density. III. Cycles and subdivisions, *submitted* (with Tung Nguyen and Paul Seymour)

185. Induced subgraph density. II. Sparse and dense sets in cographs, *submitted* (with Jacob Fox, Tung Nguyen and Paul Seymour)

184. Some results and problems on tournament structure, *submitted* (with Tung Nguyen and Paul Seymour)

183. The structure and density of k-product-free sets in the free semigroup, *submitted* (with Freddie Illingworth and Lukas Michel)

182. Shotgun assembly of random graphs, *submitted* (with Tom Johnston, Gal Kronenberg and Alexander Roberts)

181. Polynomial bounds for chromatic number. VIII. Excluding a path and a complete multipartite graph, *submitted* (with Tung Nguyen and Paul Seymour)

180. Reconstructing a point set from a random subset
of its pairwise distances,
*submitted* (with António Girão, Freddie Illingworth, Lukas Michel and Emil Powierski)

179. Induced subgraph density. I. A loglog step towards Erdős-Hajnal,
*submitted* (with Matija Bucić, Tung Nguyen and Paul Seymour)

178. Counting graphic sequences via integrated random
walks,
*submitted* (with Paul Balister, Serte Donderwinkel, Carla Groenland and Tom Johnston)

177. A multidimensional Ramsey Theorem,
*submitted* (with António Girão and Gal Kronenberg)

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

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

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

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

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

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

170. Reconstruction from smaller cards,
*submitted* (with Carla Groenland, Tom Johnston and Jane Tan)

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

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

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

*to appear*

165. Product structure of graphs with an excluded minor,

164. Flashes and rainbows in tournaments,

*published papers*

162. On a problem of El-Zahar and Erdős,

161. Defective colouring of hypergraphs,

160. Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph,

159. Pure pairs. X. Tournaments and the strong Erdős-Hajnal property,

158. Pure pairs. IX. Transversal trees,

157. Bipartite graphs with no K

156. A note on the Gyárfás-Sumner conjecture,

155. Clique covers of H-free graphs,

154. Induced paths in graphs without anticomplete cycles,

153. Graphs of large chromatic number,
*Proceedings of the International Congress of Mathematicians 2022* vol 6 (2023), 4660-4681

152. Parking on the integers,
*Annals of Applied Probability* **33** (2023), 1076-1101 (with Michał Przykucki and Alexander Roberts)

151. Best-response dynamics, playing sequences, and convergence to equilibrium in random games,
*International Journal of Game Theory* **52** (2023), 703-735 (with Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo, Bassel Tarbush and Samuel Wiese)

150. Balancing connected colourings of graphs,
*Electronic Journal of Combinatorics* **30** (2023), P1.54 (with Freddie Illingworth, Emil Powierski and Youri Tamitegama)

149. Clustered colouring of graph classes with bounded treedepth or pathwidth,
*Combinatorics, Probability and Computing* **32** (2023), 122-133 (with Sergey Norin and David Wood)

148. Decomposing random permutations into
order-isomorphic subpermutations,
*SIAM Journal on Discrete Mathematics* **37** (2023), 1252-1261 (with Carla Groenland, Tom Johnston, Dániel Korándi,
Alexander Roberts and Jane Tan)

147. Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a
forbidden submatrix,
*Journal of Combinatorial Theory, Series B* **161** (2023), 437-464 (with Paul Seymour and Sophie Spirkl)

146. Pure pairs. V. Excluding some long subdivision,
*Combinatorica* **43** (2023), 571-593 (with Paul Seymour and Sophie Spirkl)

145. Counting partitions of G_{n,1/2} with degree congruence conditions,
*Random Structures and Algorithms* **62** (2023), 564-584 (with Paul Balister, Emil Powierski and Jane Tan)

144. Polynomial bounds for chromatic number.
I. Excluding a biclique and an induced tree,
*Journal of Graph Theory* **102** (2023), 458-471 (with Paul Seymour and Sophie Spirkl)

143. Polynomial bounds for chromatic number.
IV. A near-polynomial bound for excluding the five-vertex path,
*Combinatorica* **43** (2023), 845-852 (with Paul Seymour and Sophie Spirkl)

142. Polynomial bounds for chromatic number.
VI. Adding a four-vertex path,
*European Journal of Combinatorics* **110** (2023), 103710 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

141. Polynomial bounds for chromatic number.
VII. Disjoint holes,
*Journal of Graph Theory* **104** (2023), 499-515 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

140. Erdős-Hajnal for graphs with no 5-hole,
*Proceedings of the London Mathematical Society* **126** (2023), 997-1014 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

139. Pure pairs. IV. Trees in bipartite graphs,
*Journal of Combinatorial Theory, Series B* **161** (2023), 120-146 (with Paul Seymour and Sophie Spirkl)

138. Strengthening Rödl's theorem,
*Journal of Combinatorial Theory, Series B* **163** (2023), 256-271 (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

137. Polynomial bounds for chromatic number.
III. Excluding a double star,
*Journal of Graph Theory* **102** (2022), 323-340 (with Paul Seymour and Sophie Spirkl)

136. Polynomial bounds for chromatic number.
II. Excluding a star-forest,
*Journal of Graph Theory* **101** (2022), 318-322 (with Paul Seymour and Sophie Spirkl)

135. A note on infinite antichain density,
*SIAM Journal on Discrete Mathematics* **36** (2022), 573-577 (with Paul Balister, Emil Powierski and Jane Tan)

134. Pure pairs. VI. Excluding an ordered tree,
*SIAM Journal on Discrete Mathematics* **36** (2022), 170-187 (with Paul Seymour and Sophie Spirkl)

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

132. Concatenating bipartite graphs,
*Electronic Journal of Combinatorics* **29** (2022), P2.47 (with Maria Chudnovsky, Patrick Hompe, Paul Seymour and Sophie Spirkl)

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 American Mathematical Society*
**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 American Mathematical Society* **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