A log-Sobolev inequality for the multislice, with applications

Abstract

Let $\kappa \in {\mathbb{N}}_{+}^{\ell }$ satisfy ${\kappa }_1+\cdots +{\kappa }_{\ell }=n$ and let ${\mathcal{U}}_{\kappa }$ denote the "multislice" of all strings $u$ in $[\ell {]}^n$ having exactly ${\kappa }_i$ coordinates equal to $i$, for all $i\in [\ell ]$. Consider the Markov chain on ${\mathcal{U}}_{\kappa }$, where a step is a random transposition of two coordinates of $u$. We show that the log-Sobolev constant ${\rho }_{\kappa }$ for the chain satisfies $$({\rho }_{\kappa }{)}^{-1}\le n\sum _{i=1}^{\ell }\frac{1}{2}{\log }_2(4n/{\kappa }_i),$$ which is sharp up to constants whenever $\ell$ 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.