BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Matchings on large diluted graphs : The cavity method at positive 
 temperature. - Charles Bordenave\, Université de Toulouse
DTSTART:20110314T143000Z
DTEND:20110314T153000Z
UID:TALK30209@talks.cam.ac.uk
CONTACT:Elena Yudovina
DESCRIPTION:This talk pertains to rigorous derivations of the cavity metho
 d on large graphs. The focus of the present talk will be on the maximal ma
 tching problem but other combinatorial optimization problems will be menti
 oned. \n\nWe will obtain a limit theorem for the asymptotic size of a maxi
 mum matching of a graph sequence. When the graphs are random and converge 
 in distribution to a unimodular Galton-Watson tree\, the limiting quantity
 \nturns out to satisfy a recursive distributional equation\, which we solv
 e. This leads to an explicit formula that extends the well-known result by
  Karp and Sipser for Erdos-Renyi random graphs.\n\nThis is based on a join
 t work with Marc Lelarge and Justin Salez available at http://arxiv.org/ab
 s/1102.0712\n
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR