文章基本信息

标题：A Log-Sobolev Inequality for the Multislice, with Applications
本地全文：下载
作者：Yuval Filmus ; Ryan O'Donnell ; Xinyu Wu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：124
页码：1-12
DOI：10.4230/LIPIcs.ITCS.2019.34
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：log-Sobolev inequality; small-set expansion; conductance; hypercontractivity; Fourier analysis; representation theory; Markov chains; combinatorics