A log-Sobolev inequality for the multislice, with applications

2018/09/10 by Filmus, Yuval, O'Donnell, Ryan, Wu, Xinyu · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1809.03546

Abstract

Let κ∈ ℕ₊^ℓ satisfy κ₁ + … + κ_ℓ = n and let U_κ denote the "multislice" of all strings u in [ℓ]ⁿ having exactly κ_i coordinates equal to i, for all i ∈ [ℓ]. Consider the Markov chain on U_κ, where a step is a random transposition of two coordinates of u. We show that the log-Sobolev constant ρ_κ for the chain satisfies (ρ_κ)^-1 ≤ n ∑_i=1^ℓ \tfrac12 log₂(4n/κ_i), which is sharp up to constants whenever ℓ is constant. From this, we derive some consequences for small-set expansion and isoperimetry in the multislice, including a KKL Theorem, a Kruskal--Katona Theorem for the multislice, a Friedgut Junta Theorem, and a Nisan--Szegedy Theorem.

Cited by

• Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications

Related

• A sharp log-Sobolev inequality for the multislice
• Sum-of-Squares proofs of logarithmic Sobolev inequalities on finite Markov chains
• Logarithmic Sobolev inequalities for finite Markov chains
• Upgrading MLSI to LSI for reversible Markov chains
• The KLS constant is O(log^1/4 n)