Linear Phase Transition in Random Linear Constraint Satisfaction Problems

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 en edges, where edges are equipped with randomly generated weights.