Programme

**Phase Transition Phenomena in Combinatorial Problems**

### (Workshop)

#### (supported under the

### 25th-27th January 1999

### Department of Computer Science

### University of Liverpool

*Programme*

**Monday 25th January 1999**
**10.00-13.00** Arrival and registration (Moat House, Liverpool)

**13.00-14.00** Lunch

**14.00-14.10** Opening Remarks (*Alan Gibbons*)
**14.10-15.00** Phase-Transitions: Efficient Algorithms and Combinatorial Properties (*Paul E. Dunne and Michele Zito*)

**Invited Talks**
**15.00-16.30** The Threshold Problem in Satisfiability of Random Formulae
and in Several Models of Random and Semi-random Graphs (*Paul Spirakis*)

**16.30-17.00** Coffee

**17.00-18.00** Phase-Transitions in A.I. Research (*Ian Gent*)

**Contributed Talks**
**18.00-18.30** Critical Behaviour in the Satisfiability of random k-horn formulae (*Gabriel Istrate*)

**18.30-19.00** Sharp Thresholds for `non-trivial' Satisfiability of k-horn formulae (*Paul E. Dunne*)

**19.00** Dinner.

**Tuesday 26th January 1999**

**Invited Talks**
**09.00-10.00** Phase Transition Behaviour in Constraint Satisfaction Problems (*Barbara Smith*)

**10.00-11.00** Randomly Sampling Unlabelled Structures (*Leslie Goldberg*)

**11.00-11.30** Coffee

**11.30-12.15** Sharp Thresholds of Graph Properties, and the k-SAT Problem (*Ehud Friedgut*)

**Contributed Talk**
**12.15-13.00** Random regular graphs with edge faults (*Andreas Goerdt*)

**13.00-14.00** Lunch

**Invited Talks**
**14.00-15.00** Percolation on transitive graphs: an invitation. (*Yuval Peres*)

**15.00-16.00** The Impact of the Statistical Mechanical Theory of Phase Transitions
on Other Branches of Mathematics. (*H.N.V. Temperley*)

**16.00-16.30** Coffee

**16.30-17.30** Broadcasting on trees and the Ising model. (*Yuval Peres*)

**Contributed Talks**
**17.30-18.00** A Phase Transition in Random Coin Tossing (*David Levin*)

**18.00-18.30** Typical-case complexity results from a
new type of phase transition (*Remi Monasson*)

**18.30-19.00** k-SAT, spectral gap and cut-off in Markov chains. (*Philip Knight*)

**19.00** Dinner

**Wednesday 27th January 1999**

**Invited Talk**
**09.00-10.00** Counting Complexity and Phase Transitions (*Martin Dyer*)

**Contributed Talks**

**10.00-10.30** Compound Poisson Approximations of subgraph counts in random graphs (*Dudley Stark*)

**10.30-11.00** Model clusters and failed cluters in Random k-SAT (Josh Singer)

**11.00-11.30** Coffee

**Invited Talk**
**11.30-12.30** Zero-one laws in finite model theory (*Iain Stewart*)

**13.00-14.00** Lunch

**End of Programme**