Linear Phase Transition in Random Linear Constraint Satisfaction Problems
David Gamarnik
Abstract
Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints C on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from C also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n   and m = cn for a constant c. Namely, there exists a critical value c such that, when c < c , the problem is feasible or is asymptotically almost feasible, as n  , but, when c > c , the "distance" to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies some results for maximum weight matchings in sparse random graphs G(n, cn ) on n nodes with cn edges, where edges are equipped with randomly generated weights.

1 Intro duction The primary ob jective of the present paper is studying randomly generated linear programming problems. We are interested in scaling behavior of the corresponding ob jective value and some phase transition properties, as the size of the problem diverges to infinity. Our random linear programming problems are generated in a specific way. In particular, our linear programs have a fixed number of variables per constraint and the number of variables and constraints diverges to infinity in such a way that their ratio stays a constant. Our motivation to consider this specific class of random linear programs has several sources. The main motivation is recent explosion of interest in random instances of boolean satisfiability (K-SAT) problems and the corresponding phase transition phenomenon. The main outstanding conjecture in this field states that the satisfiability property of random K-SAT problem experiences a linear phase transition as the function
 IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA. Email address: gamarnik@watson.ibm.com.

of the ratio of the number of clauses to the number of variables. Our linear programming problem can be viewed as a generalized linear programming relaxation of the integer programming formulation of such random K-SAT problem. Tightly related to the K-SAT problem are problems of maximal cardinality cuts, independent sets, matchings and other ob jects, in sparse random graphs G(n, cn ), which are graphs on n nodes and cn edges selected uniformly at random from all the possible edges, and where c > 0 is some fixed constant. For future we drop the annoying notation · , assuming that cn is always an integer. It is easy to show that all of these ob jects scale linearly in n. It is conjectured that the size of each such ob ject divided by n converges to a constant, independent of n. This convergence is established only for the case of maximum matchings using direct methods [KS81], where the limit can be computed explicitly, but is open in other cases. The main result of this paper states that the ob jective value of the random linear programming problem we consider, when divided by the number of variables converges with high probability (w.h.p.) to a certain limit. As a corollary we prove that, suitably defined, distance to feasibility in the same random linear programming problem experiences a linear phase transition, just as conjectured for random K-SAT problem. Furthermore, we show that, in a special case, the dual of this random linear programming problem is a linear programming relaxation of the maximum cardinality matching and more generally b-matching (defined later) problems in G(n, cn). We show that these relaxations are asymptotically tight as the number of nodes n diverges to infinity. As a corollary of our main result, we prove that maximum cardinality b-matching when divided by n converge to a constant. These results hold even in the weighted version, where edges are equipped with randomly independently generated nonnegative weights. Our proof technique is a combination of a very powerful local weak convergence method and martingale techniques. The local weak convergence method was developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02]. The method was specifically used by Aldous for proving the  (2) conjecture for the

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

111


That the problem experiences a sharp phase transition is proven by Friedghut [Fri99] in a much more general context. It is the linearity which is the main outstanding feature of this conjecture. One of the goals of our paper is to establish an analogue of this conjecture for generalized linear programming relaxations of the integer programming formulation (to be described below) of the random K-SAT problem. 2 Background: random K-SAT, sparse random Conjecture 2.1 is proven for the case K = 2. Specifgraphs and scaling limits ically, c = 1 was established by Goerdt [Goe92], 2 2.1 Random K-SAT problem A satisfiability or [Goe96], Chvatal and Reed [CR92], Fernandez de la K-SAT problem is a boolean constraint satisfaction Vega [dlV92]. For higher values of K many progresproblem with a special form. A collection of n variables sively sharper bounds on c (assuming it exists) are esK x1 , x2 , . . . , xn with values in {0, 1} is fixed. A boolean tablished by now. For K = 3 the best known upper and formulae of the form C1  C2  · · ·  Cm is constructed, lower bounds are 4.506 and 3.42, obtained by Dubois, where each Ci is a disjunctive clause of the form xi1  Boufkhad and Mandler [DBM00], and Kaporis, Kirousis xi2  xi3  · · ·  xiK , where exactly K variables are taken and Lalas [KKL02], respectively. It is known that c , if ¯ ¯ K from the pool x1 , . . . , xn , some with negation, some exists, approaches asymptotically 2K (log 2 + o(1)) when without. The formulae is defined to be satisfiable if an K is large, [AP]. See also [AM02], [FW02] for the reassignment of variables xi , i = 1, . . . , n to 0 or 1 can be lated results. The interest in random K-SAT problem constructed such that all the clauses take value 1. The does not stop at the threshold value. For c > c an K K-SAT problem is one of the most famous combinatorial interesting question is the maximum number of simultaoptimization problem, see [PS98]. It is well known that neously satisfiable clauses. Recently progress was made the satisfiability problem is solvable in polynomial time in this direction in [CGHS03] and [ANP]. for K = 2, and is NP-complete for K  3. Recently we have witnessed an explosion of inter- 2.2 Matching and b-matching in G(n, cn) Let G est in random instances of the K-SAT problem. This be a simple undirected graph on n nodes {1, 2, . . . , n}  was motivated by computer science, artificial intelli- [n] with an edge set E . A matching is a collection of gence and statistical physics investigations, with phase edges such that no two edges are incident to the same transition phenomena becoming the focus of a particu- node. The size of the matching is the number of edges lar attention. A random instance of a K-SAT problem in it. Let b  1 be a positive integer. A b-matching with m clauses and n variables is obtained by select- is a collection of edges A  E such that every node ing each clause uniformly at random from the entire is incident to at most b edges from A. Naturally, 1KK n n collection of 2 K ! (2K ( )) possible clauses where matching is simply a matching. Note that 2-matching K is collection of node disjoint paths and cycles. repetition of variables is (is not) allowed. In particular, Fix a constant c > 0. Let G(n, cn) denote a simfor each j = 1, 2, . . . , m, K variables xi1 , xi2 , . . . , xiK or ple undirected sparse random graph on n nodes with their negations are selected uniformly at random from cn edges selected uniformly at random from all the posthe pool xi , 1  i  n to form a clause Cj = yi1  . . . yik , sible n(n - 1)/2 edges. Denote by M(n, c, b) the size where each yir = xir or xir , equiprobably. This is done of the maximum b-matching in G(n, cn). Suppose, in ¯ for all j = 1, . . . , m independently. Whether the result- addition, the edges of G(n, cn) are equipped with raning formulae has a satisfying assignment {x1 , . . . , xn }  dom non-negative weights W edge drawn independently i,j {0, 1}n becomes a random event with respect to this ran- according to some common probability distributions. dom construction. The main outstanding conjecture for We assume W edge has a bounded support [0, B ]. Let w the random K-SAT problem is as follows. Mw (n, c, b) denote the maximum weight b-matching. It is known, that the limit limn M(n, c)/n exists and it

random assignment problem. It was used in [Ald92] to prove that the expected minimum weight matching in a complete bipartite graph converges to a certain constant. Later Aldous proved [Ald01] that this limit is indeed  (2), as conjectured earlier by Mezard and Parisi [MP87]. Since then the local weak convergence method was used for other problems (see [AS03] for a survey), and seems to be a very useful method for proving existence of limits in problems like the ones we described, and in some instances also leads to actually computing the limits of interest. To the extend that we know, our result is the first application of the local weak convergence method to establishing phase transitions in random combinatorial structures.

Conjecture 2.1. For every K  2 there exists a constant c such that a random K-SAT formulae with n K variables and m = cn clauses is satisfiable when c < c K and is not satisfiable when c > c , w.h.p. as n  . In K other words, the satisfiability experiences a linear sharp phase transition at m = c n. K

112


can be computed. This is obtained via Karp-Sipser algorithm [KS81]. The result was strengthened later by Aronson, Frieze and Pittel [APF98]. The Karp-Sipser algorithm is quite remarkable in its simplicity, however, it does not apply to the weighted case. Moreover, it is not clear how to extend the Karp-Sipser heuristic to b-matchings. In this paper we prove the existence of the limit limn Mw (n, c, b)/n for the weighted case. The proof uses the main result of the paper and the linear programming duality, though we are not able to compute the limits. Recently these limits were computed for some weight distributions [GNS03]. Naturally, our result applies to the non-weighted case ­ maximum cardinality b-matching. To the best of our knowledge this is a new result. 3 Mo del and the main results There is a natural way to describe a K-SAT problem as an integer programming problem. The variables are xi , i = 1, 2, . . . , n which take values in {0, 1}. Each clause Cj is replaced by a linear constraint of the form xi1 + (1 - xi2 ) + xi3 + . . .  1, where term (1 - x) replaces x. For example a clause C = x3  x7  x2  x4 ¯ ¯ ¯ in a 4-SAT problem is replaced by a constraint x3 + x7 + (1 - x2 ) + (1 - x4 )  1. It is easy to check that an assignment of x2 , x3 , x4 , x7 to 0 and 1 gives C value 1 if and only if the corresponding constraint is satisfied. Clearly, these constraints can be created for all the possible clauses. In the present paper we study the linear programming (LP) relaxation of this integer programming problem, where the restriction xi  {0, 1} is replaced by a weaker restriction xi  [0, 1]. Note, that this relaxation by itself is not interesting, as the assignment xi = 1/2 for all i = 1, 2, . . . , n makes all of the linear constraints feasible. However, the problem becomes non-trivial when we generalize the types of constraints that can be generated on the variables xi , and this is described in the following subsection.

select K variables xi1 , xi2 , . . . , xiK uniformly at random from xi , i = 1, 2, . . . , n. Whether the variables are selected with or without replacement turns out to be irrelevant to the results of this paper, as it is the case for random K-SAT problem. However, the order with which the variables are selected is relevant, since the constraints are not necessarily symmetric. Then we select 1  r  |C | also uniformly at random. We then generate a constraint kK
=1

(3.1)

Cj :

ark xik  br + j .

Here is an example of an instance with K = 3, n = 10, m = 4, |C | = 2. Say the first constraint C1 is 2y1 + 3y2 - y3  5, and the second constraint C2 is -y1 + y2 + 4y3  2. An example of an instance where first three constraints are type C1 and the fourth is type C2 is (2x5 + 3x4 - x9  5 + 1 )  (2x1 + 3x3 - x4  5 + 2 ) (2x2 + 3x1 - x10  5 + 3 )  (-x5 + x8 + 4x7  2 + 4 ). The central question is what are the optimal values  2 1 of Bx  xi  Bx , j  0, which minimize the sum j sub ject to the constraints Cj . That is, we consider the following linear programming problem: 1 j (3.2) Minimize
j m 1 2 sub ject to : C1 , C2 , . . . , Cm , xi  [Bx , Bx ], j  0.

In words, we are seeking a solution xj which is as K close to satisfying the constraints k=1 arik xik  br as possible. If the optimal value of this linear programming problem is zero, that is j = 0 for all j , then all of these constraints can be satisfied. Naturally, the ob jective value of the linear program (3.2) is a random variable. 3.1 Random K-LSAT problem Our setting is as We denote this random variable by LP (n, c). Note, that follows. Consider a fixed collection of K variables the linear program (3.2) is always feasible, by making y1 , y2 , . . . , yK which take values in some bounded in-  sufficiently large. In fact, clearly, in the optimal j 1 2 K terval Bx  yi  Bx and a fixed collection C of linear K solution we must have j = max(0, k=1 arik xik - br ). constraints on these variables: k=1 ar k yk  br , r = We refer to the linear program (3.2) as a random linear 1, 2, . . . , |C |, where the values ark , br are arbitrary fixed constraint satisfaction (LSAT) problem, or random Kreals. The r-th constraint can also be written in a LSAT problem. vector form ar y  br , where ar = (ar1 , . . . , arK ) and The following conditions on the set of constraints C y = (y1 , . . . , yK ). We fix c > 0 and let m = cn, will be used below. where n is a large integer. A random instance of a linear constraint satisfaction problem with n + m vari· Condition A. For any constraint ar y  br , 1  ables x1 , . . . , xn , 1 , . . . , m and m constraints is conr  |C | for any k  K and for any value z  1 2 1 2 structed as follows. For each j = 1, 2, . . . , m we per[Bx , Bx ] there exist values y1 , . . . , yK  [Bx , Bx ] form the following operation independently. We first such that yk = z and the constraint is satisfied.

113


· Condition B. There exist a positive integer l and a constant  > 0 such 1that for any K -dimensional i k i k +1 ik 1 cube I of the form kK [ l , l ], Bx  l < 2 Bxa ik integer, there exists at least one constraint , ark yk  br from C such that for every y  I , r k yk - br   . That is, every p oint of the cub e I deviates from satisfying this constraint by at least . The following is an example of an LSAT problem where Conditions A and B are satisfied. Fix K = 3. 1 2 Let Bx = 0, Bx = 1, and let C be a collection of all eight constraints of the type -y1 - y2 - y3  -7/4, -(1 - y1 ) - y2 - y3  -7/4, . . . , -(1 - y1 ) - (1 - y2 ) - (1 - y3 )  -7/4. Condition A is checked trivially. We claim that Condition B holds for l = 2 and  = 1/4. Select any cube I with side-length 1/l = 1/2. For example I = [0, 1/2] × [1/2, 1] × [1/2, 1]. Consider constraint -y1 - (1 - y2 ) - (1 - y3 )  -7/4. For any y  I we have -y1 - (1 - y2 ) - (1 - y3 )  -7/4 + 1/4 = -7/4 +  . Other cases are analyzed similarly. Consider now the following generalization of the linear program (3.2). For each j = 1, 2, . . . , m generate a random variable Wj , independently from some common distribution P{Wj  t} with a bounded support [-Bw , Bw ]. Let wx  0 and w > 0 be fixed nonnegative constants. Our random linear program in variables xi , j is con1tructed exactly as above except each s constraint Cj : r K ar k xik  br + j is replaced by (3.3) Cj : 1
r K

We now state the main result of this paper. In words, our result asserts that the scaling limit of G LP (n, c)/n exists. Theorem 3.1. For every c  0, the limit (3.6) exists w.h.p. Our first application of Theorem 3.1 is the following result. It establishes a linear phase transition property for the random K-LSAT problem. Recall that LP (n, c) is the optimal value of the linear programming problem (3.2). Theorem 3.2. There exists a constant c > 0 such K that, w.h.p. as n  , (3.7) LP (n, c) = 0, n  n lim
n

lim

G LP (n, c)  f (c) n

for al l c < c , and K (3.8) lim inf
n 

LP (n, c) > 0, n

for al l c > c . Moreover, if Condition A holds, then K c > 0, and if Condition B holds, then c < +. K K We use the local weak convergence method to prove Theorem 3.1. While our approach is very similar to the one used in [Ald92], there are several distinctive features of our problem. In particular, we do not use an infinite tree construction and instead consider a sequence of finite depth trees with some corresponding sequence of probability measures. Then we use a Martingale Convergence Theorem for the "pro jection" step. This simplifies the proofs significantly. 3.2 Maximum weighted b-matching We return to the setting of Subsection 2.2. Theorem 3.1 allows us to establish the following Theorem 3.3. For every c > 0 the limit (3.9) exists w.h.p. The proof uses linear programming duality and certain linear programming formulation of the maximum weight b-matching problem in order to relate it to our main result, Theorem 3.1. The full proof is omitted in the interest of space and can be found in full version of the paper [Gam02].
n

ark xik  br + Wj + j ,

and the ob jective function is replaced by (3.4) Minimize wx 1
in

xi + w

1
j m

j ,

sub ject to :

1 2 C1 , C2 , . . . , Cm , xi  [Bx , Bx ], j  0.

This particular form of the linear program might look unnatural at first. But note that setting Bw = wx = 0, w = 1, turns this into exactly linear program (3.2). It turns out that this general format is useful when we study b-matchings in sparse random graphs G(n, cn). We denote the optimal value of the linear program (3.4) by G LP (n, c). As before, this linear program is always feasible, by making j sufficiently large. Since we assumed w > 0, then in the optimal solution (3.5) j = max(0, ark xik - br - Wj ).

lim

Mw (n, c, b)  g (c) n

114


this neighborhood. In particular, a 1-neighborhood of x is the set of constraints Cj which contain x together with variables in these constraints. If no constraints E[G LP (n, c)] contain x, the 1-neighborhood of x is just {x}. For (4.10) (c)  lim inf . d  1, we let B(x, d, n) denote the d-neighborhood of x, n n and let  B(x, d, n) = B(x, d, n) \ B (x, d - 1, n) denote We begin by stating that in order to prove Theorem the boundary of this neighborhood, where  B (x, 0, n) is 3.1, it suffices to prove the existence of a limit (3.6) assumed to be . A chain C , C , . . . , C is defined i i i for the expected value of the optimal cost G LP (n, c). to be a cycle if C , C , . . . ,1C 2 are dristinct and i1 i2 ir-1 Indeed, note that given an instance of a linear pro- C = C . ir i1 gram (3.4), if we change one of the constraints Cj to any other constraint from the pool C and change Lemma 4.2. Let r, r be fixed constants. The expected the value of Wj to any other value in [-Bw , Bw ], and number of cycles of length r is at most (K 2 c)r . Moreleave all the other constraints intact, then the optimal over, the expected number of variables with distance at value G LP (n, c) changes by at most a constant. Using most r from some size-r cycle is at most rcr+r K 2r+r . a corollary of Azuma's inequality (see Corollary 2.27 In particular, for constants r, r the probability that a [JLR00] for the statement and a proof ), we obtain that randomly and uniformly selected variable x is at disP{|G LP (n, c)/n - E[G LP (n, c)/n]| > } converges to tance at least r from any size-r cycle is at least 1 - K zero exponentially fast for any > 0. Then the conver- rcr+r n 2r+r . gence limn E[G LP (n, c)]/n implies the convergence of G LP (n, c)/n holds w.h.p. Thus, from now on we Proof. The proof uses fairly straightforward counting concentrate on proving the existence of the limit arguments, and is quite standard line of argument in (4.11) lim
n

4 Poisson trees and some preliminary results For every c > 0 we introduce

E[G LP (n, cn)] . n

the theory of random graphs. The details of the proof can be found in [Gam02]. 2 Applying Lemmas 4.1, 4.2 we obtain the following proposition. Proposition 4.1. Given a variable x, the number of constraints in B (x, 1, n) is distributed as Pois(cK ), in the limit as n  . Also B(x, d, n) is distributed as a depth-d Poisson tree, in the limit as n  .

A random instance of a linear program (3.4) naturally leads to a sparse weighted K -hypergraph structure on a node set x1 , . . . , xn . Specifically, for each constraint Cj , 1  j  cn we create a K -edge (xi1 , . . . , xiK , r, wj ), if Cj contains exactly variables xi1 , . . . , xiK in this order, the constraint is type r, 1  r  |C | and the corresponding random variable Wj has value wj . This set of edges completely specifies the random instance. We first study the distribution of the number of edges containing a given fixed node x = x1 , . . . , xn .

We finish this section by showing how Theorem 3.1 implies Theorem 3.2. We noted before that the linear program (3.2) is a special case of the linear program Lemma 4.1. Given node x from the pool x1 , . . . , xn , (3.4), via setting Wj = 0 with probability one and by the number of edges (constraints Cj ) containing x is setting wx = 0, w = 1. Assuming limit f (c) defined in Theorem 3.1 exists, let us first show that it is a distributed as Pois(cK ), in the limit as n  . non-decreasing function of c. This is best seen by the Proof. The proof is a standard argument from the following coupling arguments. For any c1 < c2 and theory of random graphs. The details can be found in large n consider two instances of random linear program [Gam02]. 2 (3.4) with m = c1 n and m = c2 n, where the second is obtained by adding (c2 - c1 )n additional constraints to A collection of constraints Ci1 , Ci2 , . . . , Cir , 1  the first instance (we couple two instances). For each ij  m from an instance of linear program (3.4) is a realization of two linear programs, such an addition can chain of length r if for all j = 1, . . . , r - 1 the constraints only increase or leave the same the value of the ob jective Cij and Cij+1 share at least one variable. Fix a variable function. Note that in both cases we divide the ob jective x from the pool xi , 1  i  n. We say that a variable value by the same n. We conclude f (c1 )  f (c2 ). Let c  sup{c  0 : f (c) = 0}. Clearly the x  {x1 , . . . , xn } belongs to a d-neighborhood of x if x K b is connected to x y a chain of length at most d. We say set in this definition includes c = 0, and therefore is that a constraint Cj belongs to the d-neighborhood of x non-empty. The definition of c of course includes the K if all of its variables belong to it. The variables Wj and possibilities c = 0, c =  and clearly satisfies (3.7) K K j in these constraints are also assumed to be a part of and (3.8).

115


1 2 The proof of the second part of Theorem 3.2 follows (T , [Bx , Bx ]|T | × [0, B ]E (T ) × [-Bw , Bw ]E (T ) )  E , from the following proposition. where the first union runs over depth-d rooted trees T with root x1 , |T | is number of nodes in T , E (T ) is Proposition 4.2. Under Condition A, for any c < the number of constraints in T , and E is a singleton 1/K 2 , a random K-LSAT instance has the optimal value event which represents the event that B (x , d, n ) is 1 t E[LP (n, c)] = O(1). Under Condition B , there exists not a tree and contains a cycle. In particular, X (d) cK > 0 such that for al l c > cK , there exists  (c) > 0 is a countable union of compact sets. We have from ¯ ¯ for which E[LP (n, c)]   (c)n. Proposition 4.1 that limt P (d, nt )(E ) = 0. Observe that X (d)  X (d + 1) for all d. As we showed in Proof. The proof of the first part of the proposition is Proposition 4.1, the marginal distribution of T with application of "set one variable at a time" algorithm. respect to P (d, nt ) is depth-d Poisson tree, in the limit When the average degree of the corresponding hyperas t  . graph is a sufficiently small constant, this simple alRecall, that a sequence of probability measures gorithm succeeds in satisfying all but constantly many Pn defined on a joint space X is said to be weakly constraints. converging to a probability measure P if for any event The proof of the second part is application of a A  X , limn Pn (A) = P (A). We also need the standard first moment type argument. The detailed following definition and a theorem, both can be found proof of both parts can be found in [Gam02]. 2 in [Dur96].

5

Limiting probability distributions

In this and the following two sections we prove the existence of the limit (4.11). Fix c > 0 and take n to be large. We noted above that (5.12) k  1 2 j  max (|Bx | + |Bx |)K |ark | + |br | B .
1r |C |

Definition 1. A sequence of probability measures Pn on X is defined to be tight if for every > 0 there exists a compact set K  X such that lim supn P{X \ K } < . Theorem 5.1. Given a tight sequence of probability measures Pn on X there exists a probability measure P on X and a subsequence Pnt that weakly converges to P. The following proposition is a key result of this section. Proposition 5.1. For each d = 1, 2, . . . there exists a probability measure P (d) on X (d) such that P (d, nt ) weakly converges to P (d). The sequence of probability measures P (d), d = 1, 2, . . . is consistent in the sense that for every d < d , P (d) is the marginal distribution of P (d ) on X (d). The probability of the event E is equal to zero, with respect to P (d). Final ly, with respect to P (d), w j (5.15) E[wx X1 + j ] = (c), K where the summation is over al l the constraints Cj in T (d) containing the root variable x1 . Proof. The proof is similar to the one in [Ald92] for constructing a similar limiting probability distribution of optimal matchings in complete bi-partite graphs. Fix d  1. We claim that the sequence of measures P (d, nt ) is tight on X (d). By Proposition 4.1, according to the measure P (d, nt ) the neighborhood B (x1 , d, nt ) approaches in distribution a depth-d Poisson tree with parameter cK . In particular, the expected number of constraints in this neighborhood is smaller than cK + c2 K 3 + . . . + cd K 2d-1  M0 , in the limit t  .

Let, X (n), (n) denote an optimal (random) assignment of the random linear programming problem (3.4), where X (n) = (X1 , . . . , Xn ), (n) = (1 , . . . , m ). That is xi = Xi , j = j achieve the ob jective value G LP (n, c). If the set of optimal solutions contains more than one solution (in general it can be uncountable) select a solution X (n), (n) uniformly at random from this set. Define (5.13) (c) = lim inf
n

E[G LP (n, c)] , n

and find a subsequence nt , t = 1, 2, . . . along which (5.14) lim
t

E[G LP (nt , c)] = (c). nt

Fix a variable x from the set of all nt xvariables. Since labelling is chosen independent from the instance, we can take x = x1 , w.l.g. Denote by X (d, nt ), (d, nt ), W (d, nt ) the collection of X,  and W -variables which belong to the neighborhood B(x1 , d, nt ). Denote by P (d, nt ) the joint probability distribution of (B(x1 , d, nt ), X (d, nt ), (d, nt ), W (d, nt )). We omit x = x1 in the notation P (d, nt ) since, by symmetry, this joint distribution is independent of the choice of x. The support of this probability distribution is X (d) 

116


Fix > 0. By Markov's inequality the total number of constraints in B (x1 , d, nt ) is at most M with probability at least 1 - , for M > M0 / and nt sufficiently large. This implies that, moreover, each x-variable in B(x1 , d, nt ) belongs to at most M constraints (has degree at most M ) with probability at least 1 - . 1 2 Let X (d, M )  X (d) denote (T , [Bx , Bx ]|T | × E (T ) E (T ) [0, B ] × [-Bw , Bw ] ), where the trees T are restricted to have degree bounded by M . The number of trees T in X (d, M ) is finite and, as a result, the set X (d, M ) is compact, as it is a finite union of sets of the 2 1 form {T } × [Bx , Bx ]|T | × [0, B ]|E (T )| × [-Bw , Bw ]|E (T )| . We showed above that according to P (d, nt ), the neighborhood B(x1 , d, nt ) belongs to X (d, M ) with probability at least 1 - , for all sufficiently large t. This proves that the sequence of measures P (d, nt ) is tight. Then, applying Theorem 5.1, there exists a weakly converging subsequence P (d, nti ). We find such a sequence for (1) d = 1 and denote it by P (1, nt ), t = 1, 2, . . . . Again using Theorem 5.1, for d = 2 there exists a subsequence (1) of P (2, nt ) which is weakly converging. We denote (2) it by P (2, nt ). We continue this for all d obtaining (1) (2) (d) a chain of sequences nt  nt  · · ·  nt  · · · . (t) Select a diagonal subsequence n  nt from these t sequences. Then all the convergence above holds for this diagonal subsequence. In particular, for every d, P (d, n ) converges to some probability measure P (d). t Moreover, these measures, by construction, are consistent. Meaning, for every d < d , the marginal distribution of P (d ) onto X (d) is simply P (d). Since, from Proposition 4.1, the probability of the event E according to P (d, nt ) approaches zero, then the probability of the same event with respect to P (d) is just zero, for every d. To complete the proof of the proposition we need to establish (5.15). Note that in random instances of linear program (3.4), with nt x-variables, when we sum the j w expression wx Xi + K j over1 all xi , i = 1, 2, . . . , nt 1 we obtain wx Xi + w j cnt j , since each int variable j appeared in exactly K sums, corresponding to K variables in j -th constraint. From (5.14) we j w obtain that limt E[wx Xi + K j ] = (c), where the expectation is with respect to measure P (d, nt ). Since jall the random variables involved in wx Xi + w j are bounded and since P (d, n ) converges t K weakly to P (d), then the convergence carries on to the expectations. Tj is implies that with respect to P (d), h w E[wx Xi + K j ] = (c). 2

6

Filtration and a martingale with resp ect to P (d) Denote by (T (d), X (d), (d), W (d)) the random vector distributed according to P (d). Note, that T (d) and W (d) are independent from each other, first distributed as a depth-d Poisson tree, second distributed as i.i.d. with the distribution function P{W  t}. Note, that, since the measures P (d) are consistent, they correspond to a certain filtration on the increasing sequence of sets X (d), d = 1, 2, . . . . Then we can look at E[X1 |(T (d), W (d))] as a stochastic process indexed by d = 1, 2, . . . . The technical lemma that follows is needed to prove Proposition 6.1 below. This lemma is sometimes defined as tower property of conditional expectations. The proof of it can be found in many books on probability and measure theory, see for example Theorem 1.2, Chapter 4 in [Dur96]. Lemma 6.1. Let X and Y be dependent in general random variables, where X  R and Y takes values in some general set Y . Let f : Y  Y be a measurable function. Then E[E[X |Y ]|f (Y )] = E[X |f (Y )]. As above let x1 be the root of our random tree T (d) and let X1 be the corresponding random variable from the vector (T (d), X (d), (d), W (d)). Conditioned on the event that x1 belongs to at least one constraint Cj , select any such a constraint and let, w.l.g. x2 , . . . , xK be the variables in this constraint. For every k = 2, . . . , K and every d  2, consider B(xk , d)  T (xk , d), the dneighborhood of the variable xk . Note, that T (x1 , d) = T (d). Let W (xk , d) denote the collection of Wj variables corresponding to constraints in T (xk , d). To simplify the notations, we will let T W (xk , d) stand for the pair (T (xk , d), W (xk , d)). Proposition 6.1. For every k = 1, 2, . . . , K a random sequence E[Xk |T W (xk , d)], d = 1, 2, . . . is a mar1 2 tingale with values in [Bx , Bx ]. Moreover, the sequence W E[Xk |T (xd mod (K ) , d)], d = 1, 2, . . . is also a martingale. Proof. Recall, that the optimal values X (d) are a weak limit of optimal values X (d, n ), t = 1, 2, . . . . t 1 2 Then, every Xi  [Bx , Bx ] almost surely. To prove the martingale property we use Lemma 6.1, where X = Xk , Y = T W (xk , d + 1) and f is a projection function which pro jects a depth-d + 1 tree T W (xk , d + 1) onto a depth-d tree T W (xk , d) by truncating the d + 1-st layer. Applying the lemma, we obtain E[E[Xk |T W (xk , d + 1)]|T W (d)] = E[Xk |T W (xk , d)], which means precisely that the sequence is a martingale. The proof of the second part is exactly the same, we just observe that T W (x1 , 1)  T W (x2 , 2)  · · · 

117


T W (xd mod (K ) , d)  · · · , and we let f to be a pro jec- Theorem 6.1, |E[Xk |T W (xk , d)] - E[Xk |T W (xk , tK + k )]| tion of T W (xd+1 mod (K ) , d+1) onto T W (xd mod (K ) , d). becomes very small w.h.p. as d becomes large. In 2 particular, The following is a classical result from the probability theory, the proof can be found in [Dur96]. Theorem 6.1. [Martingale Convergence Theorem]. Let Xn , n = 1, 2, . . . be a martingale which takes values in some finite interval [-B , B ]. Then Xn converges almost surely to some random variable X . As a consequence, |Xn+1 - Xn | converges to zero almost surely. Let J (x1 ) denote the set of constraints Cj in T (d) containing x1 and let J (x1 ) = |J (x1 )|. Select again any constraint from J (x11 . We denote this constraint ) by C (x1 ) and let it be kK ar k yk  br + Wj + j for some 1  r  |C |, in an expanded form. Again let x2 , x3 , . . . , xK denote the other variables in this constraint. Recall that the labelling of variables in this constraint was done consistently with the labelling of the tree T , and, as a result, it is independent from the measure P (d). Let  : {1, 2, . . . , K }  {1, 2, . . . , K } specify the matching between the order in the constraint and in the tree. That is, our constraint C (x1 ) is 1 kK ar k x (k)  br + Wj + j . From (3.5) we obtain that, for the limitingkprobability measure P (d), we also ark X(k) - br - Wj ) almost surely. have j = max(0, ¯ Let Xk  E[Xk |T W (xk , d)] and let 1 ¯ ¯ (6.16) j  max(0, ark X(k) - br - Wj ).
kK

P{|E[Xk |T W (xk , d)] - E[Xk |T W (xk , tK + k )]| >  } < , for sufficiently large d. By the second part of Proposition 6.1, E[Xk |T W (xd mod (K ) , d)], d = 1, 2, . . . is a also a martingale, and again applying Theorem 6.1, we obtain that P{|E[Xk |T W (xk , tK +k )]-E[Xk |T W (x1 , tK +1)]| >  } < , Finally, again applying the first part of Proposition 6.1 to the sequence E[X1 |T W (x1 , d)], d = 1, 2, . . ., and using d - (tK + 1) < 2K , we obtain P{|E[Xk |T W (x1 , d)] - E[Xk |T W (x1 , tK + 1)]| >  } < , ¯ for sufficiently large d. Combining and using Xk = W E[Xk |T (xk , d)], we obtain (6.17) ¯ P{|Xk - E[Xk |T W (x1 , d)]| > 3 } < ,

as claimed. For every constraint Cj  J (x1 ) introduce (6.18) k ^ ark E[X(k) |T W (x1 , d)] - br - Wj ), j  max(0, k ark x(k)  br + Wj + j is the expanded where ^ form of the constraint Cj . That is j is defined just ¯ like j , except for conditioning is done on the tree T W (x1 , d) instead of T W (xk , d). Applying (6.16), (6.17) ^¯ and recalling j , j  [0, B ], we obtain that for our constraint Cj (6.19) ^ ¯ P{|j - j | > 3 K max |ark |} < K .
rk

Recall, that, according the measure P (d), J (x1 ) is distributed as Pois(cK ). Select a value M ( ) > 0 sufficiently large, so that P{J (x1 ) > M ( )} <  . Proposition 6.2. For every > 0 there existj suffi- Conditioning on the event J (x1 )  M ( ) we obtain s w ¯ ¯ ciently large d = d( ) such that E[wx X1 + K j ] <  j J ^ ¯ (c) + , where the summation is over al l the constraints P |j - j | > 3 M ( )K max |ark | (x1 )  M ( ) rk in J (x1 ).  P Cj  J (x1 ) : Proof. Fix  > 0 very small. Fix any constraint Cj  J J (x1 ) and a variable xk in it. We first show that for  ^ ¯ |j - j | > 3 K max |ark | (x1 )  M ( ) W ¯ sufficiently large d, P{|Xk - E[Xk |T (x1 , d)]| >  } <  . rk J | In other words, the expected values of Xk conditioned  ^ j - j | > 3 K max |ark | (x1 )  M ( ) ¯ M ( )P  W W on T (xk , d) and T (x1 , d) are sufficiently close to rk |P each other. For this purpose we use the martingale ^ j - j | > 3 K maxrk |ark | ¯ M ( )P  convergence theorem and Proposition 6.1. Take largest {J (x1 )  M ( )} integer t such that tK + k  d. Since, by the first part of the proposition, E[Xk |T W (xk , d)], d = 1, 2, . . . is a M ( )K  martingale, and since d - (tK + k ) < K then, applying  1 -  < M ( )(K + 1),

¯ That is j is the optimal value to be assigned to j ¯ when the variables xk take values Xk . Observe that, just ¯ k , j is a random variable. Its value is determined ¯ like X by the random tree T (xk , d) and the values of Wj , and it is different from j .

118


where the summation is over constraints in J (x1 ) and the last inequality holds provided  < 1/K . Combining with the event J (x1 ) > M , we obtain from above that, without any conditioning, j ^ ¯ P{ |j - j | > 3 M ( )K max |ark |} <
rk

M ( )(K + 1) +  < M ( )(K + 2). ^ j , j  [0, B ], then the bound above implies Since  ¯ Ej  j ^ ¯ (6.20) [ j ] - E[ j ]

Recall that J (x1 ) is distributed as Pois(cK ) and, in particular, has exponentially decaying tails. Therefore, for any > 0 we can find sufficiently small  and the corresponding M ( ) such that  M ( ) < and P{J (x1 ) > M ( )} <  . All the other values in the righthand side of the bound (6.24) are constants. Therefore, for any > 0, we can find sufficiently small  > 0 such that the right-hand side is at most (c) + . Choosing d sufficiently large for this  , we obtain the result. 2

7 Pro jection In this section we complete the proof of Theorem 3.1 by proving the existence of the limit (4.11). We use the B M ( )(K + 2) + 3 M ( )K max |ark |. limiting distribution P (d) constructed in Section 4 and rk ^ j to the random variables "pro ject" it onto any random instance of linear program Our final step is to relate  (3.4) with n x-variables and cn constraints C1 , . . . , Ccn . j , where (X (d), (d)) are drawn according to the 1 2 We construct a feasible solution xi  [Bx , Bx ], j  probability distribution P (d). Note, that for every 0, 1  i  n, 1  j  cn as follows. For each variable constraint Cj almost surely xi consider its depth-d neighborhood B(xi , d, n), where k d = d( ) is taken as in Proposition 6.2. If the B (xi , t, n) (6.21) j  ark X(k) - br - Wj , j  0. is a tree T (xi , d), then we set the value of xi equal to Xi (n)  E[Xi |T W (xi , d)], where the expectation is with By taking the conditional expectations and using the respect to the measure P (d). If, on the other hand, linearity of inequalities above, we obtain B(xi , t, n) is not a tree, then we assign any value to xi = (6.22) 1 k Xi (n), for example xi = Bx . Once we have assigned E[j |T W (x1 , d)]  ark E[X(k) |T W (x1 , d)] - br - Wj , values to x in the manner above, for every constraint ki ark xik  br + Wj + j , we set its corresponding Cj : k ark xik - br - Wj }. value of j to j (n)  max{0, E[j |T W (x1 , d)]  0, where we use the trivial equality E[Wj |T W (x1 , d)] = ^ Wj . From the definition of j in (6.18), we obtain W ^ j almost surely, with rethen E[j |T (x1 , d)]   spect to the random varij bles T W (x1 , d). As a result a j ^ j , where the summation is E[j |T W (x1 , d)]  over constraints in J (x1 ). Therefore, j j ^ (6.23) E[ j ]  E[ j ]. Recall from the last part of Proposition 5.1, that with respect to measure P (d), w j E[wx X1 + j ] = (c). K Combining this with (6.20), (6.23), and using a simple ¯ observation E[X1 ] = E[E[X1 |T W (x1 , d)]] = E[X1 ], we obtain w j ¯ w j ¯ E[wx X1 + j ]  E[wx X1 +  j ]+ K K w B M ( )(K + 2) + 3 M ( )K max |ark |
rk

Proposition 7.1. For every > 0, the solution constructed above has expected cost at most ((c) + )n for al l sufficiently large n. Since was an arbitrary constant and since (c) was defined by (5.13) the proposition shows that the assignment above satisfies limn E[G LP (n, c)]/n = (c). Therefore the proposition implies Theorem 3.1. Proof. Select one of the n variables xi uniformly and random. W.l.g. assume it is x1 . Fix 0 > 0 very small. We claim that when n is sufficiently large, we have w j (7.25) E[wx X1 (n) + j (n)]  (c) + 3 0, K where the summation is over all constraints Cj containing x1 . First let us show that this implies the statement of the proposition. Indeed, multiplying the inequality by n, and recalling that x1 was uniformly selected from 1 xi , 1  i  n, we obtain that E[wx in Xi (n) + j w j (n)]  ((c) + 3 0)n, where again we used the fact that each variable j (n) was counted exactly K times. By taking 0 < /3, we obtain the required bound.

(6.24) = (c) + w B M ( )(K + 2) + 3 M ( )K max |ark |.
rk

119


Consider the neighborhood B(x1 , d + 1, n) and sup- [AS03] D. Aldous and J. M. Steele, The objective method: Probabilistic combinatorial optimization and local weak pose first that it is not a tree. From Lemma 4.2 the convergence, Discrete Combinatorial Probability, H. probability of this event is O(1/n). Using fairly stanKesten Ed., Springer-Verlag, 2003. dard first moment techniques it can be shown that the [CGHS03] D. Coppersmith, D. Gamarnik, M. Ha jiaghayi, contribution of the corresponding term E[(wx X1 (n) + j w and G. Sorkin, Random MAXSAT, random MAXCUT, j (n)) is o(1). We omit the details and refer K and their phase transitions, Proc. 14th ACM-SIAM instead to [Gam02]. Symposium on Discrete Algorithms, 2003. Suppose now that B(x1 , d + 1, n) is a tree T (x1 , d). [CR92] V. Chvatal and B. Reed, Mick gets some (the odds Select any of the constraints containing x1 (if any exist), are on his side), Proc. 33d Symposium on Foundations and let x2 , . . . , xK be the variables in this constraints. of Computer Science (1992). Note that then B(xk , d, n) are also trees T (xk , d) and the [DBM00] O. Dubois, Y. Boufkhad, and J. Mandler, Typical corresponding values Xk (n) = E[Xk |T W (xk , d)], k = random 3-SAT formulae and the satisfiability threshold, Proc. 11th ACM-SIAM Symposium on Discrete 2, 3, . . . , K for these variables are set based only on Algorithms (2000). the observed trees T (xk , d) and values Wj , that is exactly as Xk where defined in the previous section. [dlV92] W. Fernandez de la Vega, On random 2-SAT, Unpublished manuscript (1992). Then the same correspondence holds between j (n) ¯ j . Applying Proposition 6.2, and the first part [Dur96] R. Durrett, Probability: theory and examples, and  Duxbury Press, second edition, 1996. of Proposition 5.1, that is the fact that B(x1 , n, d) [Fri99] E. Friedghut, Sharp thresholds of graph proprties, converges to T (x1 , d) distributed according to P (d), and the k-SAT problem, J. Amer. Math. Soc. 4 (1999), we obj ain that, for sufficiently large n, E[wx X1 (n) + t 1017­1054. w j (n)]  (c) + 2 0, where the second 0 comes [FW02] A. Frieze and N. Wormald, Random k-SAT: A K from approximating B (x1 , n, d) by T (x1 , d). Combining tight threshold for moderately growing k, Proceedings with the case of non-tree B (x1 , d, n) we obtain of the Fifth International Symposium on Theory and Applications of Satisfiability Testing, 2002, pp. 1­6. w j E[wx X1 (n)+ j (n)]  (c)+2 0+o(1) < (c)+3 0.[Gam02] D. Gamarnik, Linear phase transition in ranK dom linear constraint satisfaction problems, Submitfor sufficiently large n, just as required by (7.25). Acknowledgments The author gratefully acknowledges interesting and fruitful discussions with David Aldous, Michael Steele and Alan Frieze. The author is grateful to Jonathan Lee and Maxim Sviridenko for references to the results in polyhedral combinatorics. References
[Ald92] D. Aldous, Asymptotics in the random assignment problem, Probab.Th.Rel.Fields (1992), no. 93, 507­534. [Ald01] , The  (2) limit in the random assignment problem, Random Structures and Algorithms (2001), no. 18, 381­418. [AM02] D. Achlioptas and C. Moore, The asymptotic order of the random k-SAT threshold, Proc. 43d IEEE Symposium on Foundations of Computer Science (2002). [ANP] D. Achlioptas, A. Naor, and Y. Peres, On the maximum satisfiability of random formulas, Preprint. [AP] D. Achlioptas and Y. Peres, The threshold for random k-SAT is 2k (ln 2 + o(1)), Submitted. [APF98] J. Aronson, B. Pittel, and A. Frieze, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Structures and Algorithms 12 (1998), 11­178.

2

ted, 2002. [GNS03] D. Gamarnik, T. Nowicki, and Grzegorz Swirscsz, Maximum weight independent sets and matchings in sparse random graphs. exact results using the local weak convergence method, Preprint (2003). [Goe92] A. Goerdt, A threshold for unsatisfiability, Mathematical Foundations of Computer Science, 17th International Symposium. I. M. Havel and V. Koubek, Eds. Lecture Notes on Computer Science, No. 629, Springer Verlag (1992), 264­274. [Goe96] , A threshold for unsatisfiability, J. Computer and System Sciences 53 (1996), 469­486. [JLR00] S. Janson, T. Luczak, and A. Rucinski, Random graphs, John Wiley and Sons, Inc., 2000. [KKL02] A. C. Kaporis, L. M. Kirousis, and E. Lalas, The probabilistic analysis of a greedy satisfiability algorithm, 5-th International Symposium on the Theory and Applications of Satisfiability Testing, 2002, pp. 362­376. [KS81] R. Karp and M. Sipser, Maximum matchings in sparse random graphs, 22nd Annual Symposium on Foundations of Computer Science, 1981, pp. 364­375. [MP87] M. Mezard and G. Parisi, On the solution of the random link matching problem, J. Physique 48 (1987), 1451­1459. [PS98] C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity, Dover, 1998. [Ste02] J. M. Steele, Minimal spanning trees for graphs with random edge lenghts, Mathematics and Computer Science II. Algorithms, Trees, Combinatorics and Probabilities. (2002), 223­246.

120