MATH Seminar
| Title: Combinatorial approach to an interpolation method and scaling limits for sparse random graphs |
|---|
| Seminar: Combinatorics |
| Speaker: Prasad Tetali of Georgia Institute of Techonology |
| Contact: Vojtech Rodl, rodl@mathcs.emory.edu |
| Date: 2010-05-06 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: We establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on Erdos-Renyi graph G(N,c/N) and random r-regular graph G(N,r). For a variety of models, including independent sets, MAX-CUT, Coloring and K-SAT, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p., thus resolving an open problem mentioned by several experts: Wormald '99, Aldous-Steele 2003, Bollobas-Riordan 2008, as well as Janson-Thomason 2008. Our approach is based on extending and simplifying the Guerra-Toninelli interpolation method, as well as extending the work of Franz-Leone and Montanari. We provide a simpler combinatorial approach and work with the zero temperature case (optimization) directly both in the case of Erdos-Renyi graph G(N,c/N) and random regular graph G(N,r), while the previous authors handled the zero temperature case (for other models) by taking limits of positive temperature models. In addition we establish the large deviations principle for the satisfiability property for constraint satisfaction problems such as Coloring, K-SAT and NAE-K-SAT. This is joint work with D. Gamarnik (MIT) and M. Bayati (Stanford). |
See All Seminars