language-icon Old Web
English
Sign In

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.
    • Correction
    • Cite
    • Save
    • Machine Reading By IdeaReader
    23
    References
    3
    Citations
    NaN
    KQI
    []