# Linear phase transition in random linear constraint satisfaction problems

Research paper by **David Gamarnik**

Indexed on: **29 Apr '04**Published on: **29 Apr '04**Published in: **Probability Theory and Related Fields**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from 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 the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let ℳ(n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n → ∞, the limit limn→∞ ℳ(n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).