




Proof of the local REM conjecture for number partitioning II: Growing energy scales
Christian Borgs,
Jennifer Chayes,
Stephan Mertens and
Chandra Nair
Abstract
We continue our analysis of the number partitioning problem with $n$ weights chosen i.i.d. from some fixed probability distribution with density $\rho$. In Part I of this work, we established the socalled local REM conjecture of Bauke, Franz and Mertens. Namely, we showed that, as $n \to \infty$, the suitably rescaled energy spectrum above some fixed scale $\alpha$ tends to a Poisson process with density one, and the partitions corresponding to these energies become asymptotically uncorrelated. In this part, we analyze the number partitioning problem for energy scales $\alpha_n$ that grow with $n$, and show that the local REM conjecture holds as long as $n^{1/4}\alpha_n \to 0$, and fails if $\alpha_n$ grows like $\kappa n^{1/4}$ with $\kappa>0$. We also consider the SKspin glass model, and show that it has an analogous threshold: the local REM conjecture holds for energies of order $o(n)$, and fails if the energies grow like $\kappa n$ with $\kappa >0$.
BiBTeX Entry
@article{bcmn:rem2, author = {C. Borgs and J. Chayes and S. Mertens and C. Nair}, title = {Proof of the local {REM} conjecture for number partitioning {II}: Growing energy scales}, journal = {Rand.\ Struct.\ Alg.}, year = {2009}, volume = {34}, pages = {241284} }
Download:
npprem3.pdf (pdf, 260 kB)





© by Stephan Mertens
URL: http://
updated on Monday, January 18th 2010, 18:03:41 CET;