Alexander Scott

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 (October 2024)

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

Publications

submitted

204.  Subdivisions and near-linear stable sets, submitted (with Tung Nguyen and Paul Seymour)
203.  Trees and near-linear stable sets, submitted (with Tung Nguyen and Paul Seymour)
202.  Distant digraph domination, submitted (with Tung Nguyen and Paul Seymour)
201.  Graphs without a 3-connected subgraph are 4-colourable, submitted (with Édouard Bonnet, Carl Feghali, Tung Nguyen, Paul Seymour, Stéphan Thomassé and Nicolas Trotignon)
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, European Journal of Combinatorics, to appear (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 subgraph density. III. Cycles and subdivisions, submitted (with Tung Nguyen and Paul Seymour)
186.  Some results and problems on tournament structure, submitted (with Tung Nguyen and Paul Seymour)
185.  The structure and density of k-product-free sets in the free semigroup, submitted (with Freddie Illingworth and Lukas Michel)
184.  Counting graphic sequences via integrated random walks, submitted (with Paul Balister, Serte Donderwinkel, Carla Groenland and Tom Johnston)
183.  Perfect shuffing with fewer lazy transpositions, submitted (with Carla Groenland, Tom Johnston and Jamie Radcliffe)
182.  Short reachability networks, submitted (with Carla Groenland, Tom Johnston and Jamie Radcliffe)
181.  Improved bounds for 1-independent percolation on ℤⁿ, submitted (with Paul Balister, Tom Johnston and Michael Savery)
180.  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)
179.  Powers of paths and cycles in tournaments submitted (with António Girão and Dániel Korándi)
178.  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)
177.  A logarithmic bound for the chromatic number of the associahedron, submitted (with Louigi Addario-Berry, Bruce Reed and David Wood)
176.  Approximating the position of a hidden agent in a graph, submitted (with Hannah Guggiari and Alex Roberts)

to appear

published papers

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), 261-282 (with Béla Bollobás)
47.  Almost all H-free graphs have the Erdős-Hajnal property, An Irregular Mind (Szemerédi is 70), Bolyai Society Mathematical Studies, Springer, Berlin, 21 (2010) 405-414 (with Martin Loebl, Bruce Reed, Stephan Thomassé and Andrew Thomason)
46.  Max k-cut and judicious k-partitions, Discrete Math. 310 (2010), 2126-2139 (with Béla Bollobás)
45.  Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model), Séminaire Lotharingien de Combinatoire 61A (2009), Article B61Ae, 33 pages (with Alan Sokal)
44.  Uniform multicommodity flow through the complete graph with random edge-capacities, Operations Research Letters 37 (2009), 299--302 (with David Aldous and Colin McDiarmid)
43.  Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function, ACM Transactions on Algorithms (TALG) 5 (2009), Article No 45 (with Gregory Sorkin)
42.  Maximum directed cuts in acyclic digraphs, Journal of Graph Theory 55 (2007), 1-13 (with Noga Alon, Béla Bollobás, András Gyárfás and Jenő Lehel)
41.  Linear-programming design and analysis of fast algorithms for Max 2-CSP, Discrete Optimization 4 (2007), 260-287 (with Gregory Sorkin)
40.  On separating systems, European Journal of Combinatorics 28 (2007), 1068-1071 (with B. Bollobás)
39.  Computational complexity of some restricted instances of 3SAT, Discrete Applied Mathematics 155 (2007), 649-653 (with Piotr Berman and Marek Karpinski)
38.  Separating systems and oriented graphs of diameter two, Journal of Combinatorial Theory Series B 97 (2007), 193-203 (with Béla Bollobás)
37.  Partitions and orientations of the Rado graph, Transactions of the American Mathematical Society 359 (2007), no. 5, 2395--2405 (with Reinhard Diestel, Imre Leader and Stephan Thomassé)
36.  Infinite locally random graphs, Internet Mathematics 3 (2006), 321-332  (with Pierre Charbit)
35.  On dependency graphs and the lattice gas, Combinatorics, Probability and Computing 15 (2006), 253-279 (with Alan Sokal)
34.  An LP-Designed Algorithm for Constraint Satisfaction, Lecture Notes in Computer Science 4168 (2006) 588-599 (with Gregory Sorkin)
33.  Reconstructing under group actions, Graphs and Combinatorics 22 (2006), 399-419 (with Jamie Radcliffe)
32.  Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time, Combinatorics, Probability and Computing 15 (2006), 281-315 (with Gregory Sorkin)
31.  Discrepancy in graphs and hypergraphs, More sets, graphs and numbers, Bolyai Society Mathematical Studies, Springer, Berlin, 15 (2006), 33-56 (with Béla Bollobás)
30.  The repulsive lattice gas, the independent-set polynomial, and the Lovász Local Lemma, Journal of Statistical Physics 118 (2005), 1151-1261 (with Alan Sokal)
29.  Judicious partitions and related problems, in Surveys in Combinatorics 2005, 95-117, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005
28.  Reversals and transpositions over finite alphabets, SIAM Journal of Discrete Mathematics 19 (2005), 224-244 (with Jamie Radcliffe and Elizabeth Wilmer)
27.  Max Cut for random graphs with a planted partition, Combinatorics, Probability and Computing 13 (2004), 451-474 (with Béla Bollobás)
26.  Judicious partitions of bounded-degree graphs, Journal of Graph Theory 46 (2004), 131-143 (with Béla Bollobás)
25.  Finite subsets of the plane are 18-reconstructible, SIAM Journal of Discrete Mathematics, 16 (2003), 262-275 (with Luke Pebody and Jamie Radcliffe)
24.  Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, proceedings of RANDOM 2003, Lecture Notes in Computer Science 2764 (2003), 382-395 (with Gregory Sorkin)
23.  Problems and results on judicious partitions, Random Structures and Algorithms 21 (2002), 414-430 (with Béla Bollobás)
22.  On cycle lengths in graphs, Graphs and Combinatorics 18 (2002), 491-496 (with Ron Gould and Penny Haxell)
21.  Better bounds for Max Cut, Contemporary Combinatorics, Bolyai Society Mathematical Studies 10 (2002), 185-246 (with Béla Bollobás)
20.  Alternating knot diagrams, Euler circuits and the interlace polynomial, European Journal of Combinatorics 22 (2001), 1-4 (with Paul Balister, Béla Bollobás and Oliver Riordan)
19.  On induced subgraphs with all degrees odd, Graphs and Combinatorics 17 (2001), 539-553
18.  Subdivisions of transitive tournaments, European Journal of Combinatorics 21 (2000), 1067-1071
17.  Judicious partitions of 3-uniform hypergraphs, European Journal of Combinatorics 21 (2000), 289-300 (with Béla Bollobás)
16.  Exact bounds for judicious bipartitions of graphs, Combinatorica 19 (1999) 473-486 (with Béla Bollobás)
15.  Another simple proof of a theorem of Milner, Journal of Combinatorial Theory Series A 87 (1999), 379-380
14.  Reconstructing subsets of reals, Electronic Journal of Combinatorics 6 (1999), Research Paper 20, 7 pages (with Jamie Radcliffe)
13.  Induced cycles and chromatic number, Journal of Combinatorial Theory Series B 76 (1999), 150-154
12.  Reconstructing subsets of Z_n, Journal of Combinatorial Theory Series A 83 (1998), 169-187 (with Jamie Radcliffe)
11.  Judicious partitions of hypergraphs, Journal of Combinatorial Theory Series A 78 (1997), 15-31 (with Béla Bollobás)
10.  Induced trees in graphs of large chromatic number, Journal of Graph Theory 24 (1997), 297-311
9.  Reconstructing sequences, Discrete Mathematics 175 (1997), 231-238
8.  All trees contain a large induced subgraph having all degrees 1 (mod k), Discrete Mathematics 175 (1997), 35-40 (with D.M. Berman, Jamie Radcliffe, H. Wang and L. Wargo)
7.  On graph decompositions modulo k,  Discrete Mathematics 175 (1997), 289-291
6.  Better bounds for perpetual gossiping, Discrete Applied Mathematics 75 (1997), 189-197
5.  Independent sets and repeated degrees, Discrete Mathematics 170 (1997), 41-49 (with Béla Bollobás)
4.  A proof of a conjecture of Bondy concerning paths in weighted digraphs,  Journal of Combinatorial Theory Series B 66 (1996), 283-292 (with Béla Bollobás)
3.  Every tree has a large induced subgraph with all degrees odd, Discrete Mathematics 140 (1995), 275-279 (with Jamie Radcliffe)
2.  On judicious partitions of graphs, Periodica Mathematica Hungarica 26 (1993), 127-139 (with Béla Bollobás)
1.  Large induced subgraphs with all degrees odd, Combinatorics, Probability and Computing 1 (1992), 335-349

Edited book

Other publications

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)

Two joint publications

Katherine and Nick