Sannolikhets- och statistikseminarium: Sharp and sharper thresholds for random constraint satisfaction problems

  • Datum:
  • Plats: Ångströmlaboratoriet 64119
  • Föreläsare: Joel Larsson, Umeå University
  • Kontaktperson: Fiona Skerman
  • Seminarium


A celebrated theorem by Friedgut ('99) states that some random constraint satisfaction problems undergo a sharp transition (as the number of constraints grow) from satisfiable w.h.p. to unsatisfiable w.h.p. Examples include random k-SAT and q-colourability of random graphs. Unfortunately, the theorem gives no information on howsharp that transition is.

We recently discovered that combining two older theorems can shed some new light on the sharpness of such transitions.  The first, an estimate of the size of the spine of random constraint satisfaction problems (Boetcher, Istrate & Percus, '05). The second, a theorem by Aldous ('92) on general random cover problems, which has received very little attention outside the field of Markov chain theory.  (Joint with Klas Markström)