Entropy and expansion
arXiv:1811.09560 · doi:10.1214/19-AIHP1044
Abstract
Shearer's inequality bounds the sum of joint entropies of random variables in terms of the total joint entropy. We give another lower bound for the same sum in terms of the individual entropies when the variables are functions of independent random seeds. The inequality involves a constant characterizing the expansion properties of the system. Our results generalize to entropy inequalities used in recent work in invariant settings, including the edge-vertex inequality for factor-of-IID processes, Bowen's entropy inequalities, and Bollobás's entropy bounds in random regular graphs. The proof method yields inequalities for other measures of randomness, including covariance. As an application, we give upper bounds for independent sets in both finite and infinite graphs.
References in corpus (9)
- Local algorithms for independent sets are half-optimal
- Invariant Gaussian processes and independent sets on regular graphs of large girth
- Independence ratio and random eigenvectors in transitive graphs
- Weak containment and Rokhlin entropy
- Independent sets and cuts in large-girth regular graphs
- Factor of iid percolation on trees
- Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
- Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
- Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees