Professor of Mathematics, University of Oxford

Tutorial Fellow, Merton College

Leverhulme Research Fellow

Research interests: Combinatorics, probability, algorithms and related areas

Phone (Institute): 01865 615314

Phone (College): 01865 276331

Email: lastname at maths.ox.ac.uk

This year's
One-Day Meeting in Combinatorics will be on
**Wednesday 23 May 2018**.
Details about past meetings can be found here.

The Combinatorics group holds regular special events in addition to the
annual One-Day Meeting every March. 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.

116. Proof of the Kalai-Meshulam Conjecture,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

115. Exceptional graphs for the random walk,
*submitted* (with Juhan Aru, Carla Groenland, Tom Johnston, Bhargav Narayanan and Alex Roberts)

114. Size reconstructibility of graphs,
*submitted* (with Carla Groenland and Hannah Guggiari)

113. Induced subgraphs of graphs with large chromatic number.
XIII. New brooms,
*submitted* (with Paul Seymour)

112. Trees and linear anticomplete pairs,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

111. Sparse graphs with no polynomial-sized anticomplete pairs,
*submitted* (with Maria Chudnovsky, Jacob Fox, Paul Seymour and Sophie Spirkl)

110. The component structure of dense random
subgraphs of the hypercube, *submitted*
(with Colin McDiarmid and Paul Withers)

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

109. Better bounds for poset dimension and boxicity,
*submitted* (with David Wood)

108. Sparse graphs without linear anticomplete pairs,
*submitted* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

107. H-colouring P_{t}-free graphs in subexponential time,
*submitted* (with Carla Groenland, Karolina Okrasa, Paweł Rzążewski, Paul Seymour and Sophie Spirkl)

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

105. Partitioning the vertices of a torus into isomorphic
subgraphs,
*submitted* (with Marthe Bonamy and Natasha Morrison)

104. Near-domination in graphs,
*submitted* (with Bruce Reed and Paul Seymour)

103. Clustered colouring in minor-closed classes,
*submitted* (with Sergey Norin, Paul Seymour and David Wood)

102. Bad news for chordal partitions,
*Journal of Graph Theory, to appear* (with Paul Seymour and David Wood)

101. Induced subgraphs of graphs with large chromatic number.
XII. Distant stars,
*submitted* (with Maria Chudnovsky and Paul Seymour)

100. Induced subgraphs of graphs with large chromatic number.
XI. Orientations,
*submitted* (with Maria Chudnovsky and Paul Seymour)

99. Induced subgraphs of graphs with large chromatic number.
X. Holes with specific residue,
*submitted* (with Paul Seymour)

98. Induced subgraphs of graphs with large chromatic number.
VIII. Long odd holes,
*Journal of Combinatorial Theory, Series B, to appear* (with Maria Chudnovsky, Paul Seymour and Sophie Spirkl)

97. Maximising H-colourings of graphs,
*submitted* (with Hannah Guggiari)

96. Induced subgraphs of graphs with large chromatic number.
VII. Gyárfás' complementation conjecture,
*submitted* (with Paul Seymour)

95. Induced subgraphs of graphs with large chromatic number.
VI. Banana trees,
*submitted* (with Paul Seymour)

94. Stability results for graphs with a critical edge,
*European Journal of Combinatorics, to appear* (with Alexander Roberts)

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

92. Induced subgraphs of graphs with large chromatic
number. V. Chandeliers and strings,
*submitted* (with Maria Chudnovsky and Paul Seymour)

91. Disjoint paths in unions of tournaments,
*Journal of Combinatorial Theory, Series B, to appear* (with Maria Chudnovsky and Paul Seymour)

90. Induced subgraphs of graphs with large chromatic number. IV.
Consecutive holes,
*Journal of Combinatorial Theory, Series B, to appear* (with Paul Seymour)

89.
How unproportional must a graph be?,
*European Journal of Combinatorics, to appear* (with Humberto Naves and Oleg Pikhurko)

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

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

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

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

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*

*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