%~Mouliné par MaN_auto v.0.25.0 2021-08-17 11:17:52 \documentclass[AHL,Unicode,longabstracts,published]{cedram} \newcommand{\GG}{\mathbb{G}} \newcommand{\R}{\mathbb{R}} \newcommand{\PP}{\mathbb{P}} \newcommand{\EE}{\mathbb{E}} \newcommand{\cE}{\mathcal{E}} \newcommand{\frkS}{\mathfrak{S}} \newcommand{\tmix}{\tau_{\textsc{mix}}} \newcommand{\trel}{\tau_{\textsc{rel}}} \newcommand{\tmls}{\tau_{\textsc{mls}}} \newcommand{\tls}{\tau_{\textsc{ls}}} \newcommand{\am}{{\kappa_{\textsc{min}}}} \newcommand{\bfun}{\bf 1} \DeclareMathOperator{\ent}{Ent} \DeclareMathOperator{\var}{Var} \DeclareMathOperator{\triv}{triv} \DeclareMathOperator{\logs}{logs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \graphicspath{{./figures/}} \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title[A sharp log-Sobolev inequality for the multislice]{A sharp log-Sobolev inequality for the multislice} \alttitle{Une égalité de log-Sobolev optimale pour les multi-tranches} \subjclass{60J27, 60J10, 05C81} \keywords{Log-Sobolev constant, random transpositions, colored exclusion process} \author[\initial{J.} \lastname{Salez}]{\firstname{Justin} \lastname{Salez}} \address{Université Paris-Dauphine \\ \& PSL, CEREMADE - UMR 7534,\\ Place du Maréchal de Lattre de Tassigny,\\ F-75775, Paris Cedex 16, (France)} \email{justin.salez@dauphine.psl.eu} \thanks{This work was partially supported by Institut Universitaire de France.} \begin{abstract} We determine the log-Sobolev constant of the multi-urn Bernoulli--Laplace diffusion model with arbitrary parameters, up to a small universal multiplicative constant. Our result extends a classical estimate of Lee and Yau (1998) and confirms a conjecture of Filmus, O'Donnell and Wu (2018). Among other applications, we completely quantify the \emph{small-set expansion} phenomenon on the multislice, and obtain sharp mixing-time estimates for the colored exclusion process on various graphs. \end{abstract} \begin{altabstract} Nous déterminons, à une petite constante multiplicative près, la constante de log-Sobolev de la diffusion de Bernoulli--Laplace multi-urne avec paramètres arbitraires. Ce résultat étend une estimée classique de Lee et Yau (1998) et confirme une conjecture de Filmus, O'Donnell et Wu (2018). Entre autres applications, nous quantifions complètement le phénomène d'\emph{expansion des petits ensembles}, et obtenons des estimées optimales pour le temps de mélange du processus d'exclusion coloré sur divers graphes. \end{altabstract} \datereceived{2020-04-19} \dateaccepted{2021-02-05} \editor{H. Lacoin} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dateposted{2021-09-22} \begin{document} \maketitle \section{Introduction} \subsection{The multislice} Consider a sequence of positive integers $\kappa=(\kappa_1,\,\ldots,\,\kappa_L)$ of length $L\ge 2$, and set \begin{equation}\label{sum} n = \kappa_1+\,\cdots\,+\kappa_L. \end{equation} We will refer to the elements of $[L]=\{1,\,\ldots,\,L\}$ as \emph{colors}, and write $\Omega_\kappa$ for the set of $[L]-$valued sequences in which each color $\ell\in[L]$ appears exactly $\kappa_\ell$ times: \[ \Omega_\kappa := \left\{\omega=\left(\omega_1,\,\ldots,\,\omega_n\right)\in[L]^n\colon \sum_{i=1}^n{\bfun}_{(\omega_i\,=\,\ell)} = \kappa_\ell \text{ for each }\ell\in[L] \right\}. \] This natural combinatorial set is sometimes called a \emph{multislice}. It provides a canonical interpretation for the classical multinomial coefficient: \[ \left|\Omega_\kappa\right| = \binom{n}{\kappa_1,\,\ldots,\,\kappa_L}. \] The symmetric group $\frkS_n$ acts transitively on the multislice in the obvious way, by permuting coordinates. In particular, transpositions induce a natural local random walk on $\Omega_\kappa$, which consists in repeatedly picking two positions $1\le i0$ such that for all $0< k< n$, \[ \varepsilon \log \left(\frac{n^2}{k(n-k)}\right)\; \le \; \tls\left(k,n-k\right) \le \frac{2}{\log 2} \log \left(\frac{n^2}{k(n-k)}\right). \] \end{theo} The implications of Theorems~\ref{th:RT}-\ref{th:BL} are too numerous for all to be cited.\linebreak A particularly active direction consists in ``transferring'' these log-Sobolev estimates to models with less symmetry in order to obtain sharp mixing-time bounds, via the celebrated ``comparison method'' introduced by Diaconis and Saloff-Coste \cite{MR1245303,MR1233621}. Recent successful examples include the \emph{interchange process} on arbitrary graphs \cite{2018arXiv181110537A}, or the \emph{exclusion process} on high-dimensional product graphs~\cite{2019arXiv190502146H}. Beyond Markov chains, the well-known connection between log-Sobolev inequalities and \emph{hypercontractivity} provides another extremely fertile ground for applications in discrete analysis and computer science. We refer to the book~\cite[Chapters~9 \&~10]{MR3443800} for details, and to the recent work~\cite{2018arXiv180903546F} for an impressive list of references from combinatorics, computational learning, property testing or Boolean functions, where Theorems~\ref{th:RT}-\ref{th:BL} played a crucial role. Motivated by these applications, {Filmus}, {O'Donnell} and {Wu}~\cite{2018arXiv180903546F} initiated the study of the log-Sobolev constant $\tls(\kappa)$ for general $\kappa$. Their main result is as follows. \begin{theo}[{General bound, see~\cite[Theorem~1]{2018arXiv180903546F}}]\label{th:F} For any $\kappa$, \[ \tls\left(\kappa\right) \le \frac{2}{\log 2} \sum_{\ell=1}^L \log \left(\frac{4n}{\kappa_\ell}\right). \] \end{theo} Several remarkable consequences of this estimate can be found in the recent works~\cite{2018arXiv180903546F,MR4079633}. A quick comparison with Theorems~\ref{th:RW}, \ref{th:RT} and~\ref{th:BL} shows that the bound is of the right order of magnitude in the extreme case $L=2$, but is off by a factor of order $n$ at the other extreme, $L=n$. Regarding what the correct order of magnitude of $\tls(\kappa)$ should be for \emph{all} ranges of $\kappa$, {Filmus}, {O'Donnell} and {Wu} proposed the following beautifully simple dependency. \begin{conj}[{See~\cite[page~3]{2018arXiv180903546F}}]\label{cj:main} For all values of $\kappa$, \[ \tls(\kappa) \asymp \log \left(\frac{n}{\am}\right), \] where $\am:=\min\{\kappa_1,\,\ldots,\,\kappa_L\}$ and $\asymp$ means equality up to universal pre-factors. \end{conj} Note that the right-hand side decreases smoothly from $\log n $ down to $0$ as $\kappa$ becomes coarser and coarser, in agreement with Remark~\ref{rk:coarsening}. To better appreciate this conjecture, consider the \emph{single-site dynamics} obtained by projecting the multislice onto a fixed coordinate $i\in[n]$: under our transposition walk, the variable $\omega_i$ simply gets refreshed at unit rate according to the marginal distribution \[ \PP_\kappa\left(\omega_i=\ell\right) = \frac{\kappa_\ell}{n},\quad \ell\in[L]. \] The log-Sobolev constant of this trivial chain is well-known to be \[ \tls^{\triv}(\kappa) = \frac{n}{n-{2\am}}\log\left(\frac{n}{\am}-1\right) \; \asymp \; \log \left(\frac{n}{\am}\right), \] see~\cite[Theorem~A.1]{MR1410112}. Although our probability space $\Omega_\kappa$ is far from being a product space, the above conjecture asserts that the transposition walk mixes essentially as well as if the coordinates $\omega_1,\,\ldots,\,\omega_n$ were being refreshed independently. A brief look at Theorems~\ref{th:RW}, \ref{th:RT} and~\ref{th:BL} will convince the reader that this intuition is correct in all known special cases. \subsection*{Acknowledgements} The author warmly thanks Jonathan Hermon for his valuable comments on a preliminary version of this work. \section{Results} \subsection{Main estimate}\label{sec:appli} Our main result is the determination of the log-Sobolev constant $\tls(\kappa)$ for all values of the parameter $\kappa$, up to a (small) universal multiplicative constant. \begin{theo}[Log-Sobolev constant of the multislice]\label{th:main} For all values of $\kappa$, \[ \log\left(\frac{n}{\am}\right) \; \le \; \tls(\kappa) \le \frac{4}{\log 2}\log\left(\frac{n}{\am}\right). \] \end{theo} This confirms Conjecture~\ref{cj:main}. We note that the improvement upon Theorem~\ref{th:F} can be considerable if the dimension $L$ is large. Specifically, the upper bound of Filmus, {O'Donnell} and {Wu} is \emph{always} super-linear in $L$, since the convexity of $t\mapsto t\log t$~yields \begin{equation}\label{llogl} \sum_{\ell=1}^L \log \left(\frac{n}{\kappa_\ell}\right) \ge L\log L, \end{equation} for any choice of the parameter $\kappa$. In contrast, our result shows that \[ \tls(\kappa) \asymp \log L, \] as long as the vector $\kappa=(\kappa_1,\,\ldots,\,\kappa_L)$ is reasonably \emph{balanced}, in the (weak) sense that its lowest entry is of the same order as the mean entry. In particular, our estimate can be readily used to sharpen the dependency in $L$ in the various quantitative results that were derived from Theorem~\ref{th:F} in~\cite{2018arXiv180903546F}. To avoid a lengthy detour through hypercontractivity, we choose to leave the details to the reader, and to instead describe two different applications: a sharp quantification of the ``small-set expansion'' phenomenon for the multislice, and a general log-Sobolev inequality for the {colored exclusion processes}. \begin{rema}[Sharpness of constants]\label{rk:sharp} In our lower bound, the pre-factor in front of the logarithm can not be replaced by any larger universal constant, since \[ \tls(\kappa) = \left(1+o(1)\right)\log\left(\frac{n}{\am}\right), \] in the special case $\kappa=(1,n-1)$, as per Theorem~\ref{th:RW}. Regarding the upper bound, our pre-factor can not be improved by more than a $\log 2$ factor. Indeed, we will prove \[ \tls(\kappa) \ge \left(4-o(1)\right)\log\left(\frac{n}{\am}\right), \] in the special case $\kappa=(\lfloor n/2\rfloor,\lceil n/2\rceil)$, see~\eqref{sharpiota}. In fact, the possibly loose $\log 2$ term comes directly from the one appearing in Theorem~\ref{th:BL}, and any improvement of the latter will immediately imply the same improvement in our upper bound. \end{rema} \subsection{Small-set expansion} Recall that the multislice is naturally equipped with a graph structure by declaring two vertices $\omega,\omega'\in\Omega_\kappa$ to be adjacent if they differ at exactly two coordinates. Following standard graph-theoretical notation, we write $|\partial A|$ for the \emph{edge boundary} of a subset $A\subseteq \Omega_\kappa$, i.e., the set of edges having one end-point in $A$ and the other outside $A$. Let us consider the problem of finding a constant $\iota(\kappa)$, as large as possible, such that the isoperimetric inequality \begin{equation}\label{isop} \frac{|\partial A|}{|A|} \ge \iota(\kappa)\,\log\left(\frac{|\Omega_\kappa|}{|A|}\right), \end{equation} holds for all non-empty subsets $A\subseteq \Omega_\kappa$. The left-hand side measures the \emph{conductance} of $A$, i.e. the facility for the walk to escape from $A$, given that it currently lies in $A$. The presence of the logarithmic term on the other side constitutes a notable improvement upon the more standard \emph{Cheeger inequality}: instead of being constant, the right-hand side of~\eqref{isop} gets larger as the set $A$ gets smaller, thereby capturing the celebrated \emph{small-set expansion} phenomenon~\cite{2018arXiv180903546F,21923,MR1798047}. Our log-Sobolev estimate allows us to determine the fundamental quantity $\iota(\kappa)$ for all values of $\kappa$, up to a small universal constant. \begin{coro}[Small-set expansion for the multislice]\label{co:exp} The optimal constant in~\eqref{isop} satisfies \begin{equation} \frac{\log 2}{4}\frac{n}{\log\left(\frac{n}{\am}\right)} \; \le \; \iota(\kappa) \le \frac{n}{\log\left(\frac{n}{\am}\right)}. \end{equation} \end{coro} The proof will be given in Section~\ref{sec:final}. As in Remark~\ref{rk:sharp}, the universal constants appearing in our estimate can not be improved, apart from perhaps removing the $\log 2$ factor. \subsection{Colored exclusion process} A far-reaching generalization of the transposition walk on the multislice $\Omega_\kappa$ consists in allowing each of the $\binom{n}{2}$ possible transpositions to occur at a different (possibly zero) rate. More precisely, we fix a non-negative symmetric array $G=(G_{ij})_{1\,\le\,i,\,j\,\le\,n}$ (which we interpret as a weighted graph) and consider the following weighted version of the Dirichlet form~\eqref{def:dir}: \begin{equation}\label{def:weighted} \cE_{\kappa}^G\left(f,g\right) := \frac{1}{2}\sum_{1\,\le\,i\,<\,j\,\le\,n}G_{ij}\,\EE_\kappa\left[\left(\nabla^{ij}f\right)\left(\nabla^{ij}g\right)\right]. \end{equation} The canonical setting -- to which we shall here stick for simplicity -- consists in taking $G$ to be the transition matrix of the simple random walk on a regular graph, which we henceforth identify with $G$. The resulting process is known as the $\kappa-$\emph{colored exclusion process} on $G$, see~\cite{MR2629990}. By varying the parameter $\kappa$, we obtain a rich family of diffusion models on $G$ including: \begin{enumerate} \item the \emph{simple random walk} on $G$, when $\kappa=(1,n-1)$; \item the \emph{$k-$particle exclusion process} on $G$, when $\kappa=(k,n-k)$; \item the \emph{interchange process} on $G$, when $\kappa=(1,\,\ldots,\,1)$. \end{enumerate} Comparing the mixing properties of these three processes constitutes a rich and active research problem, see~\cite{2018arXiv181110537A,MR2629990,MR3978223,hermon2018exclusion, MR3069380,MR2244427,MR3077529, MR2023023}. Perhaps the most celebrated result in this direction is the remarkable fact that their Poincaré constants coincide, as conjectured by Aldous and established by Caputo, Liggett and Richthammer~\cite{MR2629990}. \begin{theo}[Insensitivity of the Poincaré constant, see~\cite{MR2629990}]\label{th:aldous} The Poincaré constant $\trel(\kappa,G)$ of the $\kappa-$colored exclusion process on $G$ does not depend on $\kappa$. In particular, it equals the Poincaré constant $\trel(G)$ of the simple random walk on $G$. \end{theo} In a sense, this result asserts that the Poincaré constant is too ``rough'' to capture the influence of the color profile $\kappa$ on the mixing properties of the colored exclusion process. It is thus natural to turn one's attention to the finer log-Sobolev constant. \begin{enonce}[remark]{Question} How does the log-Sobolev constant $\tls(\kappa,G)$ depend upon $\kappa$? \end{enonce} Our main result answers this question in the simple \emph{mean-field} setting, where $G$ is the complete graph. However, it implies an estimate of $\tls(\kappa,G)$ for arbitrary $G$, by means of the celebrated ``comparison method'' introduced by Diaconis and Saloff-Coste~\cite{MR1245303,MR1233621}. A particularly pleasant observation here is that we do not even need to build a comparison theory for the colored exclusion process: we can simply recycle the one that has already been developed for the interchange process. Specifically, let $c(G)$ be the smallest number such that the functional inequality \begin{equation}\label{comp} \cE_{(1,\,\ldots,\,1)}(f,f) \le c(G)\,\cE_{(1,\,\ldots,\,1)}^G(f,f), \end{equation} holds for all $f\colon\Omega_{(1,\,\ldots,\,1)}\to\R$. This fundamental quantity is known as the \emph{comparison constant} of the interchange process on $G$. It was shown in~\cite{2018arXiv181110537A} that \[ c(G) \lesssim \tmix(G), \] where $\lesssim$ means inequality up to a universal multiplicative constant, and where $\tmix(G)$ denotes the mixing time of the simple random walk on $G$. It is in fact believed that \begin{equation}\label{conj} c(G) \asymp \trel(G), \end{equation} see~\cite[Conjecture~2]{2019arXiv190502146H}. This refinement, inspired by an analogous relation for the \emph{Zero-Range process}~\cite{MR3984254}, is already known to hold for several natural families of graphs ranging from low-dimensional tori~\cite{2018arXiv181110537A} to high-dimensional products~\cite{2019arXiv190502146H}. Those estimates can be combined with our main result to yield a general log-Sobolev inequality for the colored exclusion process (see Section~\ref{sec:colored} for details): \begin{coro}[Log-Sobolev inequality for colored exclusion]\label{co:colored} We have \[ \max\left\{2\trel(G),\log\left(\frac{n}{\am}\right)\right\} \; \le \; \tls\left(\kappa, G\right) \le \frac{4}{\log 2}\,c(G)\log\left(\frac{n}{\am}\right). \] \end{coro} To appreciate the sharpness of this general inequality, note that the lower and upper bounds are of the same order in the following two generic situations: \begin{itemize} \item For families of graphs with $c(G)\asymp 1$ (i.e. ``well-connected'' graphs), we obtain \[ \tls\left(\kappa, G\right) \asymp \log\left(\frac{n}{\am}\right), \] exactly as in the mean-field case. Note that this potentially constitutes a considerable extension of our main result, since the class of graphs satisfying $c(G)\asymp 1$ is believed to contain all expanders, as per~\eqref{conj}. \item For graphs satisfying the conjecture~\eqref{conj}, in the regime $\am\ge \varepsilon n$, we get \[ \tls\left(\kappa, G\right) \asymp \trel(G). \] This constitutes a multi-colored generalization of several estimates obtained for two colors, including~\cite[Theorem~4]{MR1675008} on the cycle and~\cite[Corollary~2.6]{2019arXiv190502146H} on the hypercube. \end{itemize} \begin{rema}[Mixing times] One of the many interests of those log-Sobolev estimates is that they provide powerful controls on the strong $L^\infty-$mixing time of the process, see e.g., \cite{MR2341319}. Let us here just give one concrete example: on the $d-$dimensional hypercube, our work implies that the balanced colored exclusion process with an arbitrarily fixed number $L\ge 2$ of colors mixes in time $\Theta(d^2)$. The special case $L=2$ of this statement had been conjectured several years ago by Wilson~\cite{MR2023023}, and was settled only recently~\cite{hermon2018exclusion}. \end{rema} We end this section with an intriguing possibility, which arises naturally in view of Theorem~\ref{th:aldous} and of what happens in the mean-field case (Lemma~\ref{pr:insensitive}). \begin{enonce}{Question}[Sensitivity of the modified log-Sobolev constant] Can the choice of the parameter $\kappa$ affect $\tmls(\kappa,G)$ by more than a universal multiplicative constant? \end{enonce} A negative answer would, in particular, substantially improve our current knowledge on the mixing times of the interchange and exclusion processes on general graphs. We note that, unlike our main result, the estimate on $\tmls(\kappa)$ provided by Lemma~\ref{pr:insensitive} can \emph{not} be directly transferred to more general graphs, since the modified log-Sobolev constant is notoriously \emph{not} amenable to comparison techniques. This severe drawback constitutes a strong point in favor of log-Sobolev inequalities (as opposed to their modified versions) for mean-field interacting particle models, and was one of the motivations for the present work. \section{Proofs} \subsection{General strategy}\label{sec:strategy} Let us start with an elementary but crucial observation about the multislice. \begin{rema}[Recursivity]\label{obs} If $\omega$ is uniformly distributed on $\Omega_\kappa$, then the conditional law of $(\omega_1,\,\ldots,\,\omega_{i-1},\omega_{i+1},\,\ldots,\,\omega_n)$ given $\{\omega_i=\ell\}$ is uniform on $\Omega_{\kappa'}$, where \[ \kappa'=\left(\kappa_1,\,\ldots,\,\kappa_{\ell-1},\kappa_\ell-1,\kappa_{\ell+1},\,\ldots,\,\kappa_L\right). \] \end{rema} Such a simple recursive structure suggests the possibility of proving Theorem~\ref{th:main} by induction over the dimension $n$, using the ``chain rule'' for entropy (see formula~\eqref{decomposition} below). This is in fact a classical strategy for establishing functional inequalities, known as the ``martingale method''. Introduced by Lu \& Yau~\cite{MR1233852} in the context of Kawasaki and Glauber dynamics, it has been successfully applied to various interacting particle systems~\cite{Cap,MR2094147,MR2023890,hermon2019entropy,MR1675008,MR1483598}, as well as other Markov chains enjoying an appropriate recursive structure~\cite{MR1944012,2018arXiv180903546F,2019arXiv190202775H,1181997,MR2099650}. In particular, this is how Theorem~\ref{th:BL} was proved. However, as explained in detail in~\cite{2018arXiv180903546F}, moving from the special case $L=2$ covered by Theorem~\ref{th:BL} to the general case studied in Theorem~\ref{th:F} significantly complicates the inductive argument, resulting in the loose $L\log L$ dependency mentioned at~\eqref{llogl}. Here we introduce two simple ideas to bypass those complications and prove Conjecture~\ref{cj:main}: \begin{enumerate}\romanenumi \item \label{3.1.i} instead of just a single site, we condition on a whole region being colored with $\ell\in[L]$; \item \label{3.1.ii}when averaging the contributions from the various colors, we assign more weight to rare colors, which are the ones which really govern $\tls(\kappa)$. More precisely, our decomposition~\eqref{dec:ent} below gives weight $1-\frac{\kappa_\ell} n$ to the $\ell-$colored region, whereas the traditional uniform average over all sites would give it the weight $\frac{\kappa_\ell}{n}$. \end{enumerate} Let us now implement those ideas. We fix an observable $f\colon\Omega_\kappa\to\R_+$ once and for all. To lighten notation, we drop the index $\kappa$ from our expectations, and write simply \[ \ent(f) := \EE\left[f\log f\right] -\EE[f]\log\EE[f], \] for the entropy of $f$. If $Z$ is a random variable on $\Omega_\kappa$, we define the \emph{conditional entropy} of $f$ given $Z$ by simply replacing all expectations with conditional expectations, i.e. \[ \ent(f|Z) := \EE[f\log f|Z] -\EE[f|Z]\log\EE[f|Z]. \] We then have the following elementary ``chain rule'': \begin{equation}\label{decomposition} \ent(f) = \EE\left[\ent(f|Z)\right]+\ent\left(\EE[f|Z]\right). \end{equation} The choice $Z=\omega_i$ is of course natural in light of Remark~\ref{obs}, and this was the one adopted in the proofs of Theorems~\ref{th:BL} and~\ref{th:F}. However, as mentioned in~\eqref{3.1.i} above, we choose here to condition instead on the whole $\ell-$colored region \begin{equation}\label{def:xio} \xi_\ell := \left\{i\in[n]\colon \omega_i=\ell\right\}. \end{equation} With $Z=\xi_\ell$, the formula~\eqref{decomposition} becomes \begin{equation}\label{dec:set} \ent(f) = \EE\left[\ent\left(f|\xi_\ell\right)\right]+\ent\left(\EE\left[f|\xi_\ell\right]\right). \end{equation} Following our second idea~\eqref{3.1.ii}, we multiply both sides of this identity by the ``unusual'' weight $1-\frac{\kappa_\ell}{n}$ and then sum over all colors $\ell\in[L]$. Recalling~\eqref{sum}, we obtain the following formula, which will constitute the basis of our induction: \begin{equation}\label{dec:ent} (L-1)\ent(f) = \underbrace{\sum_{\ell=1}^L\left(1-\frac{\kappa_\ell}{n}\right)\EE\left[\ent\left(f|\xi_\ell\right)\right]}_{\Sigma_1}+\underbrace{\sum_{\ell=1}^L\left(1-\frac{\kappa_\ell}{n}\right)\ent\left(\EE\left[f|\xi_\ell\right]\right)}_{\Sigma_2}. \end{equation} Our main task will consist in estimating the two terms $\Sigma_1$ and $\Sigma_2$ on the right-hand side, in terms of the log-Sobolev constants of certain lower-dimensional multislices. More precisely, we let $\kappa^{\setminus \ell}$ denote the parameter obtained from $\kappa$ by removing the $\ell-$th entry, i.e. \[ \kappa^{\setminus\ell} := \left(\kappa_1,\,\ldots,\,\kappa_{\ell-1},\kappa_{\ell+1},\,\ldots,\,\kappa_L\right), \] and we will prove in the next section that \begin{align} \Sigma_1 & \le (L-2)\max_{\ell\,\in\,[L]}\left\{\tls\left(\kappa^{\setminus\ell}\right)\right\}\cE_\kappa\left(\sqrt{f},\sqrt{f}\right);\label{pr:first}\\ \Sigma_2 & \le \max_{\ell\,\in\,[L]}\left\{2\left(1-\frac{\kappa_\ell}n\right)\tls\left(\kappa_\ell,n-\kappa_\ell\right)\right\}\cE_\kappa\left(\sqrt{f},\sqrt{f}\right).\label{pr:second} \end{align} Plugging those estimates into~\eqref{dec:ent} yields a log-Sobolev inequality for $\Omega_\kappa$, thereby establishing the following recursive estimate. \begin{prop}[Recursive log-Sobolev estimate]\label{pr:recursive} We have \[ (L-1)\tls\left(\kappa\right) \le (L-2)\max_{\ell\,\in\,[L]}\left\{\tls\left(\kappa^{\setminus \ell}\right)\right\}+\max_{\ell\,\in\,[L]}\left\{2\left(1-\frac{\kappa_\ell}n\right)\tls\left(\kappa_\ell,n-\kappa_\ell\right)\right\}. \] \end{prop} From this, the upper bound in Theorem~\ref{th:main} follows by an easy induction over the number $L$ of colors, using the known log-Sobolev estimate for $L=2$ (Theorem~\ref{th:RT}). The details, as well as the proof of the lower bound, are provided in Section~\ref{sec:final}. \subsection{Main recursion} This section is devoted to proving the two technical estimates~\eqref{pr:first} and~\eqref{pr:second} which, in view of the decomposition~\eqref{dec:ent}, establish Proposition~\ref{pr:recursive}. \begin{proof}[Proof of the first estimate~\eqref{pr:first}] Conditionally on the $\ell-$colored region $\xi_\ell$, $f$ may be regarded as a function of the remaining coordinates $(\omega_i\colon i\in[n]\setminus \xi_\ell)$, which form a uniformly distributed element of $\Omega_{\kappa^{\setminus\ell}}$. Consequently, the log-Sobolev inequality for the multislice $\Omega_{\kappa^{\setminus\ell}}$ gives \[ \ent\left(f|\xi_\ell\right) \le \frac{\tls\left(\kappa^{\setminus\ell}\right)}{2(n-\kappa_\ell)}\sum_{1\,\le\,i\,<\,j\,\le\,n}\EE\left[\left(\nabla^{ij}\sqrt{f}\right)^2{\bfun}_{(i\,\notin\,\xi_\ell,\,j\,\notin\,\xi_\ell)}\middle|\xi_\ell\right]. \] Note that the event in the indicator can be rewritten as $\{\ell\notin\{\omega_i,\omega_j\}\}$, and that we may impose the restriction $\{\omega_i\ne\omega_j\}$ at no cost, since $\nabla^{ij}\sqrt{f}=0$ on the event $\{\omega_i=\omega_j\}$. Taking expectations and rearranging, we arrive at \[ \left(1-\frac{\kappa_\ell}{n}\right)\EE\left[\ent\left(f|\xi_\ell\right)\right] \le \frac{\tls\left(\kappa^{\setminus\ell}\right)}{2n}\sum_{1\,\le\,i\,<\,j\,\le\,n}\EE\left[\left(\nabla^{ij}\sqrt{f}\right)^2{\bfun}_{\left(\omega_i\,\ne\,\omega_j\right)}{\bfun}_{\left(\ell\,\notin\,\left\{\omega_i,\,\omega_j\right\}\right)}\right]. \] Summing over all $\ell\in[L]$ yields \[ \sum_{\ell=1}^L\left(1-\frac{\kappa_\ell}{n}\right)\EE\left[\ent\left(f|\xi_\ell\right)\right] \le (L-2)\max_{\ell\,\in\,[L]}\left\{\tls\left(\kappa^{\setminus\ell}\right)\right\}\cE_\kappa\left(\sqrt{f},\sqrt{f}\right), \] which is exactly the claim made at~\eqref{pr:first}. \end{proof} \begin{proof}[Proof of the second estimate~\eqref{pr:second}] Fix $\ell\in[L]$, and let us write \begin{equation}\label{def:F} \EE\left[f|\xi_\ell\right] = F\left(\xi_\ell\right), \end{equation} for some non-negative function $F=F_\ell$. The distribution of $\xi_\ell$ is uniform over all $\kappa_\ell-$element subsets of $[n]$, and this is precisely the stationary distribution of the occupied set in the $\kappa_\ell-$particle Bernoulli--Laplace diffusion model on $n$ sites. When applied to the function $F$, the log-Sobolev inequality for this process reads as follows: \begin{equation}\label{induced} \ent\left(\EE\left[f|\xi_\ell\right]\right) \le \frac {\tls\left(\kappa_\ell,n-\kappa_\ell\right)}{2n}\sum_{1\,\le\,i\,<\,j\,\le\,n}\EE\left[\left(\sqrt{F\left(\xi_\ell^{ij}\right)}-\sqrt{F\left(\xi_\ell\right)}\right)^2\right], \end{equation} where $A^{ij}$ denotes the set obtained from $A$ by swapping the membership status of $i$ and $j$: \[ A^{ij} := \begin{cases} A\cup\{j\}\setminus\{i\} & \text{if }i\in A,j\notin A\\ A\cup\{i\}\setminus\{j\} & \text{if }i\notin A,j\in A\\ A & \text{else.} \end{cases} \] Now, fix $1\le i