Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

Details Combinatorial approach to the interpolation method and scaling limits in sparse random graphs Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

2009-12-12

arxiv.org/abs/0912.2444v2

Mathematics

Probability

26 pages

Scientific paper

We establish the existence of free energy limits for several combinatorial models on Erd{\"o}s-R\'{e}nyi graph $\G(N,\lfloor cN\rfloor)$ 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. This resolves an open problem which was proposed by Aldous as one of his six favorite open problems. It was also mentioned as an open problem in several other places. Our approach is based on extending and simplifying the interpolation method of Guerra and Toninelli and Franz and Leone. Among other applications, this method was used to prove the existence of free energy limits for Viana-Bray and K-SAT models on Erd{\"o}s-R\'{e}nyi 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{\"o}s-R\'{e}nyi graph $\G(N,\lfloor cN\rfloor)$ and random regular graph $\G(N,r)$. In addition we establish the large deviations principle for the satisfiability property of the constraint satisfaction problems Coloring, K-SAT and NAE-K-SAT for the $\G(N,\lfloor cN\rfloor)$ random graph model.

Affiliated with

Also associated with

No associations

Rating

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial approach to the interpolation method and scaling limits in sparse random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-533394