Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 12/05/2009
14:30 		Mihyun Kang (TU Berlin) (TU Berlin) Combinatorial Theory Seminar Add to calendar L3
How to count planar graphs
Tue, 19/05/2009
14:30 		Jozef Skokan (LSE) Combinatorial Theory Seminar Add to calendar L3
Multicolour Ramsey numbers for cycles
For graphs $ L_1,\dots,L_k $, the Ramsey number $ R(L_1,\ldots,L_k) $ is the minimum integer $ N $ such that for any edge-colouring of the complete graph $ K_N $ by $ k $ colours there exists a colour $ i $ for which the corresponding colour class contains $ L_i $ as a subgraph. In this talk, we shall discuss recent developments in the case when the graphs $ L_1,\dots,L_k $ are all cycles and $ k\ge2 $.
Tue, 26/05/2009
14:30 		Mark Walters (QMUL) Combinatorial Theory Seminar Add to calendar L3
Hamilton cycles in random geometric graphs
The Gilbert model of a random geometric graph is the following: place points at random in a (two-dimensional) square box and join two if they are within distance $ r $ of each other. For any standard graph property (e.g.  connectedness) we can ask whether the graph is likely to have this property.  If the property is monotone we can view the model as a process where we place our points and then increase $ r $ until the property appears.  In this talk we consider the property that the graph has a Hamilton cycle.  It is obvious that a necessary condition for the existence of a Hamilton cycle is that the graph be 2-connected. We prove that, for asymptotically almost all collections of points, this is a sufficient condition: that is, the smallest $ r $ for which the graph has a Hamilton cycle is exactly the smallest $ r $ for which the graph is 2-connected.  This work is joint work with Jozsef Balogh and Béla Bollobás
Tue, 02/06/2009
14:30 		Ben Green (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Approximate groups
Let $ A $ be a finite set in some ambient group. We say that $ A $ is a $ K $-approximate group if $ A $ is symmetric and if the set $ A.A $ (the set of all $ xy $, where $ x $, $ y $ lie in $ A $) is covered by $ K $ translates of $ A $. I will illustrate this notion by example, and will go on to discuss progress on the "rough classification" of approximate groups in various settings: abelian groups, nilpotent groups and matrix groups of fixed dimension. Joint work with E. Breuillard.
Tue, 16/06/2009
14:30 		Amin Coja-Oghlan (Edinburgh) Combinatorial Theory Seminar Add to calendar L3
A better algorithm for random k-SAT
Let $ F $ be a uniformly distributed random $ k $-SAT formula with $ n $ variables and $ m $ clauses. We present a polynomial time algorithm that finds a satisfying assignment of $ F $ with high probability for constraint densities $ m/n < 2^k \ln(k)/k $. Previously no efficient algorithm was known to find solutions with a non-vanishing probability beyond $ m/n=1.817 2^k/k $ [Frieze and Suen, Journal of Algorithms 1996]. The density $ 2^k \ln(k)/k $ matches the replica symmetry breaking transition, whose existence was recently established rigorously [Achlioptas and Coja-Oghlan, FOCS 2008].

For any corrections/updates to these listings, please contact seminars [-at-] maths [dot] ox [dot] ac [dot] uk.

Syndicate content