2003/09/26 by David Gamarnik, Gamarnik, David, Tomasz Nowicki +3 · 2 citations
Mathematics · #05C80 #05C90 #60C05 #60J85 #82B26 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:05C90 #msc:60C05 #msc:60J85 #msc:82B26
paper · pdf · doi:10.48550/arxiv.math/0309441
31 pages
arxiv created 2003/09/26 · arxiv updated 2009/12/01
Let G(n,c/n) and Gr(n) be an n-node sparse random graph and a sparse random r-regular graph, respectively, and let \cal I(n,r) and \cal I(n,c) be the sizes of the largest independent set in G(n,c/n) and Gr(n). The asymptotic value of \cal I(n,c)/n as n→∞, can be computed using the Karp-Sipser algorithm when c≤ e. For random cubic graphs, r=3, it is only known that .432≤\liminfn \cal I(n,3)/n ≤ \limsupn \cal I(n,3)≤ .4591 with high probability (w.h.p.) as n→∞, as shown by Frieze and Suen and by Bollobas, respectively. In this paper we assume in addition that the nodes of the graph are equipped with non-negative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit limn \cal I(n,c)/n can be computed exactly even when c>e, and limn \cal I(n,r)/n can be computed exactly for some r≥ 2. For example, when the weights are exponentially distributed with parameter 1, limn \cal I(n,2e)/n≈ .5517, and limn \cal I(n,3)/n≈ .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider.