Oxford-Warwick-London (OWL) Meeting 2007
Combinatorics, Probability and Statistical Mechanics
A joint seminar afternoon on Combinatorics, Probability and Statistical Mechanics will be held at the University of Oxford on Wednesday 31 January, 2007. The schedule is as follows:
2.00 - 3.00: Benedetto Scoppola (Rome) Some spin glass ideas applied to the clique problem
3.00 - 4.00: John Cardy (Oxford) Random curves in critical lattice models and Stochastic Loewner Evolution
4.00 - 5.00: Tea
5.00 - 6.00: Anton Bovier (Berlin) Recent progress on the spin glass problem
The talks will take place in room L3 in the Mathematical Institute. Here are instructions on getting to the Mathematical Institute.
All are welcome, and we can provide some financial support for students to attend. Students wanting to claim support should bring travel receipts.
For further information, please contact Alex Scott.
This event is part of a Oxford-Warwick-London Series supported by the London Mathematical Society and the British Combinatorial Committee. The next meeting will take place in Warwick on Thursday, 10 May 2007, the details of which can be found here: OWL Joint Seminar (Warwick).
Programme
Recent progress on the spin glass problem
I review the connections between combinatorial optimisation, spin glasses, and extreme value theory of correlated random processes in high dimension. I will highlight universality aspects of the emerging asymptotic random structures. Specifically I will discuss the universality of energy level spacing, first found in the number partitioning problem, and the role of Poisson cascades in the Parisi solution of the Sherrington-Kirkpatrick model.
Random curves in critical lattice models and Stochastic Loewner Evolution
Stochastic Loewner Evolution (SLE) gives a set of conformally invariant measures on curves in the plane, labelled by a parameter kappa. These are conjectured to be the scaling limit of the measure on discrete curves in certain lattice models. However for generic kappa these models (for example the Potts model for generic Q) do not have local Boltzmann weights. In the first part of this talk I introduce local models based on the Coxeter ADE diagrams which overcome this drawback, at least for rational kappa. In the second half, I discuss the progress and difficulties of the programme to prove that the scaling limit of these curves is indeed given by SLE.
Some spin glass ideas applied to the clique problem
In this talk I introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. I will focus on the maximum clique problem and I will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising.