Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2001-02-14
Phys. Rev. E 64, 036115 (2001)
Physics
Condensed Matter
Statistical Mechanics
21 pages, 7 figs, to appear in Phys. Rev. E
Scientific paper
10.1103/PhysRevE.64.036115
We develop a systematic cluster expansion for dilute systems in the highly dilute phase. We first apply it to the calculation of the entropy of the K-satisfiability problem in the satisfiable phase. We derive a series expansion in the control parameter, the average connectivity, that is identical to the one obtained by using the replica approach with a replica symmetric ({\sc rs}) {\it Ansatz}, when the order parameter is calculated via a perturbative expansion in the control parameter. As a second application we compute the free-energy of the Viana-Bray model in the paramagnetic phase. The cluster expansion allows one to compute finite-size corrections in a simple manner and these are particularly important in optimization problems. Importantly enough, these calculations prove the exactness of the {\sc rs} {\it Ansatz} below the percolation threshold and might require its revision between this and the easy-to-hard transition.
Cugliandolo Leticia F.
Semerjian Guilhem
No associations
LandOfFree
Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses 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 Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-432719