Factor of iid percolation on trees
2014
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.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
23
References
3
Citations
NaN
KQI