Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method
| dc.creator | Gamarnik, David | |
| dc.creator | Nowicki, Tomasz | |
| dc.creator | Swirscsz, Grzegorz | |
| dc.date | 2003-09-26 | |
| dc.date.accessioned | 2026-07-07T05:01:29Z | |
| dc.date.available | 2026-07-07T05:01:29Z | |
| dc.description | Let $G(n,c/n)$ and $G_r(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 $G_r(n)$. The asymptotic value of ${\cal I}(n,c)/n$ as $n\to\infty$, can be computed using the Karp-Sipser algorithm when $c\leq e$. For random cubic graphs, $r=3$, it is only known that $.432\leq\liminf_n {\cal I}(n,3)/n \leq \limsup_n {\cal I}(n,3)\leq .4591$ with high probability (w.h.p.) as $n\to\infty$, 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 $\lim_n {\cal I}(n,c)/n$ can be computed exactly even when $c>e$, and $\lim_n {\cal I}(n,r)/n$ can be computed exactly for some $r\geq 2$. For example, when the weights are exponentially distributed with parameter 1, $\lim_n {\cal I}(n,2e)/n\approx .5517$, and $\lim_n {\cal I}(n,3)/n\approx .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. | |
| dc.description | 31 pages | |
| dc.identifier | https://arxiv.org/abs/math/0309441 | |
| dc.identifier | http://arxiv.org/abs/math/0309441 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68689 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05;60J85;82B26;05C80;05C90 | |
| dc.title | Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method | |
| dc.type | text |