22 March - 26 March 2010
Isaac Newton Institute for Mathematical Sciences, Cambridge, UK
Workshop Organisers: Takis Konstantopoulos (Heriot-Watt) and Kavita Ramanan (Brown University).
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 programmeStochastic Processes in Communication Sciences (11 January to 2 July 2010) Participants | Application | Accommodation and Cost
Title: 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)