22 March - 26 March 2010

Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

**Workshop Organisers:** Takis Konstantopoulos (*Heriot-Watt*) and Kavita Ramanan (*Brown University*).

**Workshop Programme Committee:** Vivek Borkar (*Tata Institute of Fundamental Research*), Serguei Foss (*Heriot-Watt University*), Peter Glynn (*Stanford*),

Bruce Hajek (*University of Illinois*), Frank Kelly (*Cambridge*), P.R. Kumar (*University of Illinois*), Tom Kurtz (*University of Wisconsin-Madison*), Jean Mairesse (*LIAFA*), Philippe Robert (*INRIA*), John Tsitsiklis (*MIT*) and Ruth Williams (*University of California, San Diego*)

in association with the Newton Institute programme

Stochastic Processes in Communication Sciences (11 January to 2 July 2010) Participants | Application | Accommodation and CostTitle: Matchings and rank for random diluted graphs

We study matchings on a sequence of random graphs that converge locally to trees. Inspired by techniques from random matrix theory, we rigorously prove the validity of the cavity method for the computation of the entropy. At a positive temperature, the cavity equations are interpreted as equations for the local marginals of the Boltzmann Gibbs distribution in the space of matchings on a (possibly) infinite tree. These equations also appear in the computation of the asymptotic rank of the adjacency matrices of the random graphs. We also define a determinantal process on the tree which is the limit at positive temperature of the matchings on the sequence of graphs. (joint work with Charles Bordenave and Justin Salez)

Local Information | Newton Institute Map | Stochastic Processes in Communication Sciences | Workshops | Newton Institute Home Page