2002/10/31 by David Gamarnik, Gamarnik, David
Mathematics · Physics and Astronomy · #60C05 #60G42 #60K35 #82B20 #82B26 #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #math-ph #math.MP #math.PR #msc:60C05 #msc:60G42 #msc:60K35 #msc:82B20 #msc:82B26
paper · pdf · doi:10.48550/arxiv.math/0210470
26 pages, expanded version
arxiv created 2003/05/14 · arxiv updated 2009/11/30
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 ask the following question: is the resulting linear programming problem feasible? We show that the feasibility property experiences a linear phase transition, when n diverges to infinity and m=cn for some constant c. Namely, there exists a critical value c* such that, when c<c*, the system is feasible or is asymptotically almost feasible, as n increases, but, when c>c*, the "distance" from feasibility is at least a positive constant independent of n. Our results are obtained using powerful local weak convergence methods developed by Aldous and Steele. 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 limn M(n,c)/n exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n,cn).