PDF《MAXIMUM INDEPENDENT SETS ON RANDOM》

s solution to the random assignment problem [4] and Talagrand'

s proof of Parisi'

s formula for the SherringtonC Kirkpatrick spin-glass model [23], many of the most important ideas remain at the level of conjecture. We believe that recent developments, including our own previous work [13, 12], make it possible to establish thresholds predicted by this theory for many such models. The natural approach to studying the independence ratio is the (?rst and second) moment method applied to the number of Znα of independent sets of ?xed density α. Indeed, an analogous approach correctly determines the asymptotic independence number for the dense Erd?s-Rényi random graph [18]. On sparse random graph ensembles, however, the second moment approach fails to locate the sharp transition. Due to the sparsity of the graph, almost every independent set can be locally perturbed in a linear number of places: thus the existence of a single independent set implies the existence of a cluster of exponentially many independent sets, all related by sequences of local perturbations. Moreover the expected cluster size remains exponentially large even beyond the ?rst moment threshold ― thus there is a regime below the ?rst moment threshold where it overcomes the ?rst moment, causing the second moment to be exponentially large compared with the ?rst moment squared. From statistical physics, the (mostly heuristic) understanding of this phenomenon is that as α exceeds roughly plog dq{d, the solution space of independent sets becomes shattered into exponentially many well-separated clusters [9]. This geometry persists up to a further (conjectured) structural transition where the solution space condensates onto the largest clusters. In the non-trivial regime between the condensation and satis?ability transitions, most independent sets are concentrated within a bounded number of clusters according to the MAXIMUM INDEPENDENT SETS ON RANDOM REGULAR GRAPHS

3 theory from statistical physics. This within-cluster correlation then dominates the moment calculation, causing the failure of the second moment method. In this paper, we determine the exact threshold by a novel approach which rigorizes the 1rsb heuristic from statistical physics, which suggests that we count clusters of independent sets rather than the sets themselves. Our proof has several new ideas which we now describe. The ?rst is that most clusters of maximal (or locally maximal) independent sets can be given the following simple combinatorial description. A cluster is encoded by a con?guration of what we call the frozen model , which takes values in t0, 1, fuV where the f ( free ) spins indicate the local perturbations within the cluster, and come in matched pairs corresponding to swapping occupied/unoc........