Semerjian G, Cugliandolo L F
Laboratoire de Physique Théorique de l'Ecole Normale Supérieure, 24 rue Lhomond, 75231 Paris Cedex 05, France.
Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Sep;64(3 Pt 2):036115. doi: 10.1103/PhysRevE.64.036115. Epub 2001 Aug 28.
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 (RS) 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 RS ansatz below the percolation threshold, and might require its revision between this and the easy-to-hard transition.
