Entropy and expansion
From MaRDI portal
Cheeger constantexpansionindependent setentropy inequalitylocal algorithmfactor-of-IIDgraph isoperimetry
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Measures of information, entropy (94A17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Group actions on combinatorial structures (05E18)
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'as'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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4049676 (Why is no real title available?)
- A measure-conjugacy invariant for free group actions
- Cubic graphs with small independence ratio
- Entropy inequalities for factors of IID
- Explicit isoperimetric constants and phase transitions in the random-cluster model
- Factor of iid percolation on trees
- Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
- Independence ratio and random eigenvectors in transitive graphs
- Invariant Gaussian processes and independent sets on regular graphs of large girth
- Isoperimetric Constants of (d,f)-Regular Planar Graphs
- Limits of local algorithms over sparse random graphs
- Local algorithms for independent sets are half-optimal
- Mutual information decay for factors of i.i.d.
- On large‐girth regular graphs and random processes on trees
- On the almost eigenvectors of random regular graphs
- On the independence and chromatic numbers of random regular graphs
- Perfect matchings as IID factors on non-amenable groups
- Processes on unimodular random networks
- Properties of regular graphs with large girth via local algorithms
- Replica bounds by combinatorial interpolation for diluted spin systems
- Some intersection theorems for ordered sets and graphs
- Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
- The Independence Ratio of Regular Graphs
- The ergodic theory of free group actions: entropy and the f-invariant
Cited in
(8)- Block factorization of the relative entropy via spatial mixing
- Distributed algorithms for fractional coloring
- Shearer's inequality and infimum rule for Shannon entropy and topological entropy
- Entropy and volume growth
- Nonlinear recombinations and generalized random transpositions
- On mixing of Markov chains: coupling, spectral independence, and entropy factorization
- Entropy inequalities for factors of IID
- Typicality and entropy of processes on infinite trees
This page was built for publication: Entropy and expansion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028943)
