论文标题
对称组的超收缩率
Hypercontractivity on the symmetric group
论文作者
论文摘要
超平等的不平等是分析的基本结果，在整个离散数学，理论计算机科学，组合学等过程中，许多应用程序都有许多应用。到目前为止，这种不平等的变体主要是针对产品空间的，这提出了一个问题，即类似结果是否在非产物域中。 我们考虑对称组，$ s_n $，这是最基本的非产品域之一，并在其上建立了超收入不平等。我们的不平等对于$ s_n $上的\ emph {global functions}的类别最有效，在限制输入的$ o（1）$坐标时，其$ 2 $ norm仍然很小，并且断言低数量的全球函数的$ q $ - norms很小，$ q $ - norms，对于$ q> 2 $。 作为应用程序，我们显示： 1。超越立方体上$ d $不平等的类似物，断言低级全球功能的质量很小。我们还展示了如何使用这种不平等来绑定交替组$ a_n $中全球无产品集的大小。 2。用于全局函数的$ s_n $的转置cayley图上的等轴测不平等，类似于KKL定理以及布尔hypercube中的小型扩展属性。 3。在某些参数方面，多板的超额收缩不等式和kruskal-katona定理的稳定版本。
The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. So far, variants of this inequality have been proved mainly for product spaces, which raises the question of whether analogous results hold over non-product domains. We consider the symmetric group, $S_n$, one of the most basic non-product domains, and establish hypercontractive inequalities on it. Our inequalities are most effective for the class of \emph{global functions} on $S_n$, which are functions whose $2$-norm remains small when restricting $O(1)$ coordinates of the input, and assert that low-degree, global functions have small $q$-norms, for $q>2$. As applications, we show: 1. An analog of the level-$d$ inequality on the hypercube, asserting that the mass of a global function on low-degrees is very small. We also show how to use this inequality to bound the size of global, product-free sets in the alternating group $A_n$. 2. Isoperimetric inequalities on the transposition Cayley graph of $S_n$ for global functions, that are analogous to the KKL theorem and to the small-set expansion property in the Boolean hypercube. 3. Hypercontractive inequalities on the multi-slice, and stability versions of the Kruskal--Katona Theorem in some regimes of parameters.
