pith. sign in

arxiv: 1809.03546 · v1 · pith:R7AYJXEUnew · submitted 2018-09-10 · 🧮 math.PR · cs.DM· math.CO

A log-Sobolev inequality for the multislice, with applications

classification 🧮 math.PR cs.DMmath.CO
keywords kappamultislicetheoremchainconstantcoordinateslog-sobolevmathcal
0
0 comments X
read the original abstract

Let $\kappa \in \mathbb{N}_+^\ell$ satisfy $\kappa_1 + \dots + \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} \leq n \sum_{i=1}^{\ell} \tfrac{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.