A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on Wednesday 5 June 2013.
Schedule and abstracts can be found below.
11.00 am Peter Keevash (QMUL)
Dynamic concentration of the triangle-free process
11.55 am Amin Coja-Oghlan (Frankfurt)
Chasing the k-SAT threshold
12.50 pm Lunch
2.15 pm Jean-Sébastien Sereni (CNRS)
Questions (and answers) about fractional colourings
3.10 pm Penny Haxell (Waterloo)
Morphing planar graph drawings
4.05 pm Tea
4.30 pm Ben Green (Cambridge)
Counting sumsets and the clique number of random Cayley graphs, revisited
Anyone interested is welcome to attend, and no registration is required. Some funds may be available to contribute to the expenses of research students who wish to attend the meeting. Further details can be obtained from Alex Scott (scott at maths.ox.ac.uk). Support for this event by the London Mathematical Society and the British Combinatorial Committee is gratefully acknowledged.
Amin Coja-Oghlan (Frankfurt),
Chasing the k-SAT threshold
Let F be a random Boolean formula in conjunctive normal form over n Boolean variables with m clauses of length k. The existence of a (non-uniform) sharp threshold for the satisfiability of such formulas is well known [Friedgut 1999]. However, despite considerable effort the precise location of this phase transition remains unknown for any k greater than 2. The best previous upper and lower bounds differ by an additive k ln 2/2 [Achlioptas, Peres 2003]. In this talk I present an improved lower bound, which reduces the gap to ~0.19. The proof is inspired by the cavity method of statistical mechanics.
Ben Green (Cambridge), Counting sumsets and the clique number of random Cayley graphs, revisited
I will describe various techniques for counting the number of sets A of integers with |A| = k and |A+A| = m, where A + A is the set of sums a + a' with a, a' in A. An application of these results and some work I did 10 years ago is a proof that a random Cayley graph on vertex set Z/NZ has clique number (2 + o(1))log N, the same as for a random graph (10 years ago I was only able to get a bound of 160 log N). Joint work with Rob Morris.
Penny Haxell (Waterloo), Morphing planar graph drawings
A morph between two planar drawings Γ_0 and Γ_1 of a graph G is a continuous family of drawings Γ_t indexed by time t in [0,1]. The morph preserves straight-line planarity if all intermediate drawings Γ_t are straight-line planar drawings, in which case each Γ_t is determined by the positions of its vertices. Morphing arises naturally in a number of contexts including computer graphics, motion planning and medical imaging. We discuss efficient algorithmic solutions to the morphing problem that address various aspects such as the simplicity of the trajectory of each vertex throughout the morph.
Peter Keevash (QMUL), Dynamic concentration of the triangle-free process
The triangle-free process begins with an empty graph on $n$ vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. We determine the asymptotic number of edges in the maximal triangle-free graph at which the triangle-free process terminates. We also bound the independence number of this graph, which gives an improved lower bound on the Ramsey numbers R(3,t): we show R(3,t) is greater than (1/4-o(1))t^2/\log t, which is within a 4+o(1) factor of the best known upper bound. Furthermore, we determine which bounded size subgraphs are likely to appear in the maximal triangle-free graph produced by the triangle-free process: they are precisely those triangle-free graphs with maximal average density at most 2. This is joint work with Tom Bohman.
Jean-Sébastien Sereni (CNRS), Questions (and answers) about fractional colourings
Heckman and Thomas conjectured that every triangle-free graph with maximum degree at most 3 has fractional chromatic number at most 14/5. After introducing the background for such a statement, I will try to convey the essential ideas of a recent confirmation of the conjecture (found with Z. Dvorak and J. Volec). In addition, several open questions about fractional colourings will be presented