Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
We establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on Erd¨os-R´enyi 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 pr...
| Autores principales: | , , |
|---|---|
| Otros Autores: | |
| Formato: | Artículo |
| Lenguaje: | en_US |
| Publicado: |
Association for Computing Machinery
2011
|
| Acceso en línea: | http://hdl.handle.net/1721.1/65914 https://orcid.org/0000-0001-8898-8778 |
| _version_ | 1826188094170202112 |
|---|---|
| author | Bayati, Mohsen Gamarnik, David Tetali, Prasad |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bayati, Mohsen Gamarnik, David Tetali, Prasad |
| author_sort | Bayati, Mohsen |
| collection | MIT |
| description | We establish the existence of free energy limits for several
sparse random hypergraph models corresponding to certain
combinatorial models on Erd¨os-R´enyi 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, (see Conjecture 2.20
in [Wor99], as well as [Ald],[BR],[JT08] and [AS03]).
Our approach is based on extending and simplifying the
interpolation method of Guerra and Toninelli. Among other
applications, this method was used to prove the existence
of free energy limits for Viana-Bray and K-SAT models on
Erd¨os-R´enyi graphs. The case of zero temperature was treated
by taking limits of positive temperature models. We provide
instead a simpler combinatorial approach and work with the
zero temperature case (optimization) directly both in the
case of Erd¨os-R´enyi graph G(N, c/N) and random regular
graph G(N, r). In addition we establish the large deviations
principle for the satisfiability property for constraint
satisfaction problems such as Coloring, K-SAT and NAEK-
SAT. For example, let p(c, q,N) and p(r, q,N) denote,
respectively, the probability that random graphs G(N, c/N)
and G(N, r) are properly q-colorable. We prove the existence
of limits of N[superscript −1] log p(c, q,N) and N[superscript 1] log p(r, q,N),
as N -> infinity. |
| first_indexed | 2024-09-23T07:54:30Z |
| format | Article |
| id | mit-1721.1/65914 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:54:30Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/659142022-09-23T09:32:23Z Combinatorial approach to the interpolation method and scaling limits in sparse random graphs Bayati, Mohsen Gamarnik, David Tetali, Prasad Sloan School of Management Gamarnik, David Gamarnik, David We establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on Erd¨os-R´enyi 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, (see Conjecture 2.20 in [Wor99], as well as [Ald],[BR],[JT08] and [AS03]). Our approach is based on extending and simplifying the interpolation method of Guerra and Toninelli. Among other applications, this method was used to prove the existence of free energy limits for Viana-Bray and K-SAT models on Erd¨os-R´enyi graphs. The case of zero temperature was treated by taking limits of positive temperature models. We provide instead a simpler combinatorial approach and work with the zero temperature case (optimization) directly both in the case of Erd¨os-R´enyi graph G(N, c/N) and random regular graph G(N, r). In addition we establish the large deviations principle for the satisfiability property for constraint satisfaction problems such as Coloring, K-SAT and NAEK- SAT. For example, let p(c, q,N) and p(r, q,N) denote, respectively, the probability that random graphs G(N, c/N) and G(N, r) are properly q-colorable. We prove the existence of limits of N[superscript −1] log p(c, q,N) and N[superscript 1] log p(r, q,N), as N -> infinity. National Science Foundation (U.S.) (grant DMS- 0701043) National Science Foundation (U.S.) (grant CCR-0910584) 2011-09-21T19:16:17Z 2011-09-21T19:16:17Z 2010-06 Article http://purl.org/eprint/type/JournalArticle 978-1-4503-0050-6 http://hdl.handle.net/1721.1/65914 Bayati, Mohsen, David Gamarnik, and Prasad Tetali. “Combinatorial Approach to the Interpolation Method and Scaling Limits in Sparse Random Graphs.” Proceedings of the 42nd ACM Symposium on Theory of Computing - STOC ’10. Cambridge, Massachusetts, USA, 2010. 105. https://orcid.org/0000-0001-8898-8778 en_US http://dx.doi.org/10.1145/1806689.1806706 Proceedings of the 42nd ACM Symposium on Theory of Computing Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery Prof. Gamarnik via Alex Caracuzzo |
| spellingShingle | Bayati, Mohsen Gamarnik, David Tetali, Prasad Combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| title | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| title_full | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| title_fullStr | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| title_full_unstemmed | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| title_short | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| title_sort | combinatorial approach to the interpolation method and scaling limits in sparse random graphs |
| url | http://hdl.handle.net/1721.1/65914 https://orcid.org/0000-0001-8898-8778 |
| work_keys_str_mv | AT bayatimohsen combinatorialapproachtotheinterpolationmethodandscalinglimitsinsparserandomgraphs AT gamarnikdavid combinatorialapproachtotheinterpolationmethodandscalinglimitsinsparserandomgraphs AT tetaliprasad combinatorialapproachtotheinterpolationmethodandscalinglimitsinsparserandomgraphs |