Alexander Scott

Professor of Mathematics, University of Oxford
Tutorial Fellow, 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

 

 

This year's One-Day Meeting in Combinatorics will be on Thursday 5 June 2014.  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.


Publications

75.  On Saturated k-Sperner Systems, submitted (with Natasha Morrison and Jonathan Noel)
74.  Disjoint induced subgraphs of the same order and size, submitted (with Béla Bollobás, Teeradej Kittipassorn and Bhargav Narayanan)
73.  Disjoint dijoins, submitted (with Maria Chudnovsky, Katherine Edwards, Ringi Kim and Paul Seymour)
72.  Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, submitted (with Peter Jeavons and Lei Xu; journal version of #62)
71.  Intersections of random hypergraphs and tournaments, submitted (with Béla Bollobás)
70.  Excluding pairs of graphs, Journal of Combinatorial Theory, Series B, to appear (with Maria Chudnovsky and Paul Seymour)
69.  Complete monotonicity for inverse powers of some combinatorially defined polynomials, Acta Mathematica, to appear (with Alan Sokal)
68.  Intersections of hypergraphs, Journal of Combinatorial Theory, Series B, to appear (with Béla Bollobás)
67.  For most graphs H, most H-free graphs have a linear homogeneous set, Random Structures and Algorithms, to appear (with Ross J. Kang, Colin McDiarmid and Bruce Reed)
66.  The parameterised complexity of list problems on graphs of bounded treewidth, submitted (with Kitty Meeks)
65.  Disjoint paths in tournaments, submitted (with Maria Chudnovsky and Paul Seymour)
64.  Structure of random r-SAT below the pure literal threshold, submitted (with Gregory Sorkin)

63.  Hypergraphs of bounded disjointness, SIAM Journal on Discrete Mathematics 28 (2014), 372-384 (with Elizabeth Wilmer)
62.  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)
61.  Substitution and χ-boundedness, Journal of Combinatorial Theory, Series B 103 (2013), 567-586 (with Maria Chudnovsky, Irena Penev and Nicolas Trotignon)
60.  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é)
59.  The complexity of Free-Flood-It on 2xn boards, Theoretical Computer Science 500 (2013), 25-43 (with Kitty Meeks)
58.  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é)
57.  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)
56.  Spanning trees and the complexity of flood-filling games, FUN 2012, Lecture Notes in Computer Science 7288 (2012), 282-292; journal version. (with Kitty Meeks)
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, Algorithms ESA 2011, Lecture Notes in Computer Science 6942 (2011), 799-810; journal version: SIAM Journal of Discrete Mathematics, to appear (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 of 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 Jamie Radcliffe and Luke Pebody)
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 Zn, 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 kDiscrete 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 digraphsJournal 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

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)

 

 


Two joint publications

Katherine and Nick