Virág, Bálint and Rahman, Mustazee (2017) LOCAL ALGORITHMS FOR INDEPENDENT SETS ARE HALF-OPTIMAL. ANNALS OF PROBABILITY, 45 (3). pp. 1543-1577. ISSN 0091-1798
|
Text
1402.0485v2.pdf Download (351kB) | Preview |
Abstract
We show that the largest density of factor of i.i.d. independent sets in the d-regular tree is asymptotically at most (log d)/d as d -> infinity. This matches the lower bound given by previous constructions. It follows that the largest independent sets given by local algorithms on random d-regular graphs have the same asymptotic density. In contrast, the density of the largest independent sets in these graphs is asymptotically 2(log d)/d. We prove analogous results for Poisson-Galton-Watson trees, which yield bounds for local algorithms on sparse Erdos-Renyi graphs.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | LIMITS; NUMBER; Girth; Matchings; Regular graphs; Random graphs; Factor of i.i.d.; local algorithm; Independent set |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 12 Feb 2018 07:33 |
| Last Modified: | 12 Feb 2018 07:33 |
| URI: | http://real.mtak.hu/id/eprint/74282 |
Actions (login required)
 |
Edit Item |
