## DMTCS Proceedings, Discrete Random Walks, DRW'03

Font Size:
DMTCS Conference vol AC (2003), pp. 113-126

## Discrete Random Walks, DRW'03

### DMTCS Conference Volume AC (2003), pp. 113-126

author: David Gamarnik Linear Phase Transition in Random Linear Constraint Satisfaction Problems Random K-SAT, Satisfiability Threshold, Linear Programming, Sparse Random Graphs 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 [1992, 2000], Aldous and Steele [2003], Steele [2002] 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 M(n,c) denote maximum weight matching in G(n, cn) . We prove that when c is a constant and n→∞ , the limit lim n→∞ M(n,c)/n, exists, with high probability. We further extend this result to maximum weight b -matchings also in G(n,cn) . If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. David Gamarnik (2003), Linear Phase Transition in Random Linear Constraint Satisfaction Problems, in Discrete Random Walks, DRW'03, Cyril Banderier and Christian Krattenthaler (eds.), Discrete Mathematics and Theoretical Computer Science Proceedings AC, pp. 113-126 For a corresponding BibTeX entry, please consider our BibTeX-file. dmAC0111.ps.gz (56 K) dmAC0111.ps (136 K) dmAC0111.pdf (152 K)