Entropy and expansion

DOI10.1214/19-AIHP1044zbMath1465.94034arXiv1811.09560OpenAlexW3093486955MaRDI QIDQ2028943

Bálint Virág, Endre Csóka, Viktor Harangi

Publication date: 3 June 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

entropy inequalityexpansionCheeger constantindependent setlocal algorithmfactor-of-IIDgraph isoperimetry

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Measures of information, entropy (94A17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Group actions on combinatorial structures (05E18)

Related Items

Block factorization of the relative entropy via spatial mixing ⋮ Typicality and entropy of processes on infinite trees ⋮ On mixing of Markov chains: coupling, spectral independence, and entropy factorization ⋮ Distributed algorithms for fractional coloring

Cites Work

• Unnamed Item
• Properties of regular graphs with large girth via local algorithms
• Perfect matchings as IID factors on non-amenable groups
• Independence ratio and random eigenvectors in transitive graphs
• A measure-conjugacy invariant for free group actions
• The ergodic theory of free group actions: entropy and the \(f\)-invariant
• Some intersection theorems for ordered sets and graphs
• On the independence and chromatic numbers of random regular graphs
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Cubic graphs with small independence ratio
• Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
• Replica bounds by combinatorial interpolation for diluted spin systems
• Explicit isoperimetric constants and phase transitions in the random-cluster model
• Local algorithms for independent sets are half-optimal
• Entropy inequalities for factors of IID
• On the almost eigenvectors of random regular graphs
• Processes on unimodular random networks
• Isoperimetric Constants of (d,f)-Regular Planar Graphs
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• The Independence Ratio of Regular Graphs
• On large‐girth regular graphs and random processes on trees
• Mutual information decay for factors of i.i.d.
• Factor of IID Percolation on Trees
• Limits of local algorithms over sparse random graphs