Factor of IID Percolation on Trees

DOI10.1137/15M1021362zbMath1351.05206arXiv1410.3745MaRDI QIDQ5298168

Mustazee Rahman

Publication date: 13 December 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.3745

zbMATH Keywords

percolationrandom regular graphsinduced forestlocal algorithmsfactor of iid

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Stationary stochastic processes (60G10) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (6)

Suboptimality of local algorithms for a class of max-cut problems ⋮ On the almost eigenvectors of random regular graphs ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Entropy and expansion ⋮ Mutual information decay for factors of i.i.d. ⋮ Entropy inequalities for factors of IID

Cites Work

• Unnamed Item
• Unnamed Item
• Percolation with small clusters on random graphs
• Properties of regular graphs with large girth via local algorithms
• Perfect matchings as IID factors on non-amenable groups
• Construction of pure states in mean field models for spin glasses
• Independence ratio and random eigenvectors in transitive graphs
• A measure-conjugacy invariant for free group actions
• On the independence and chromatic numbers of random regular graphs
• A note on the independence number of triangle-free graphs. II
• Uniform spanning forests
• Local algorithms for independent sets are half-optimal
• Invariant random perfect matchings in Cayley graphs
• Large independent sets in regular graphs of large girth
• Limits of locally-globally convergent graph sequences
• Probability on Trees and Networks
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Ramanujan graphings and correlation decay in local algorithms
• Induced Forests in Regular Graphs with Large Girth
• Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
• Borel oracles. An analytical approach to constant-time algorithms
• The Independence Ratio of Regular Graphs
• Decycling numbers of random regular graphs
• On large‐girth regular graphs and random processes on trees
• Factors of IID on Trees
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Limits of local algorithms over sparse random graphs

This page was built for publication: Factor of IID Percolation on Trees