2026-07-29T11:26:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10127 2024-03-06T10:45:26Z ddc:004 open_access

A Log-Sobolev Inequality for the Multislice, with Applications Filmus, Yuval O'Donnell, Ryan Wu, Xinyu log-Sobolev inequality small-set expansion conductance hypercontractivity Fourier analysis representation theory Markov chains combinatorics Let kappa in N_+^l satisfy kappa_1 + *s + kappa_l = n, and let U_kappa denote the multislice of all strings u in [l]^n having exactly kappa_i coordinates equal to i, for all i in [l]. Consider the Markov chain on 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} <= n * sum_{i=1}^l 1/2 log_2(4n/kappa_i), which is sharp up to constants whenever l 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuval Filmus and Ryan O'Donnell and Xinyu Wu 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.34 urn:nbn:de:0030-drops-101279 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.34 eng https://creativecommons.org/licenses/by/3.0/legalcode