Factor of iid percolation on trees

Abstract

We study invariant percolation processes on the d-regular tree that are obtained as a factor of an iid process. We show that the density of any factor of iid site percolation process with finite clusters is asymptotically at most (log d)/d as d tends to infinity. This bound is asymptotically optimal as it can be realized by independent sets. One implication of the result is a (1/2)-factor approximation gap, asymptotically in d, for estimating the density of maximal induced forests in locally tree-like d-regular graphs via factor of iid processes.

new version: some new references included

References in corpus (6)

• Local algorithms for independent sets are half-optimal
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Ramanujan graphings and correlation decay in local algorithms
• Independence ratio and random eigenvectors in transitive graphs
• Invariant random matchings in Cayley graphs
• Percolation with small clusters on random graphs

Cited by in corpus (3)

• Suboptimality of local algorithms for a class of max-cut problems
• Entropy and expansion
• Correlation bound for distant parts of factor of IID processes