Sharp threshold and scaling window for the integer partitioning problem
Christian Borgs, Jennifer Chayes, Boris G. Pittel · 2001
We consider the problem of partitioning n integers chosen randomly between 1 and 2^m into two subsets such that the discrepancy, the absolute value of the difference of their sums, is minimized. A partition is called perfect if the optimum discrepancy is 0 when the sum of all n integers in the original set is even, or 1 when the sum is odd. Parameterizing the random problem in terms of κ = m/n, we prove that the problem has a sharp threshold at κ = 1, in the sense that for κ < 1, there are many perfect partitions with probability tending to 1 as n \to \infty, while for κ 1, there are no perfect partitions with probability tending to 1. Moreover, we show that the derivative of the so-called entropy is discontinuous at κ=1.