论文标题
扩散禁止交叉点问题的近似值
Spread approximations for forbidden intersections problems
论文作者
论文摘要
我们开发了一种新的方法来近似集合家庭，与现有的“ $δ$系统方法”和“ junta近似方法”进行补充。我们称之为“传播近似方法”的方法是基于$ r $ sprec的家族的概念，并建立在Alweiss，Lovett，Wu和Zhang的最新突破性的基础上，以期为Erd \ h Os-Rado“ Sunflower usplower猜想”。我们的方法可以在各种稀疏设置中起作用。 为了证明方法的多功能性和强度，我们介绍了它在禁止交叉问题上的几个应用，包括定期相交家庭大小的范围，解决了新范围内的设置以及$ t $ to的解决方案的ERD \ hos-sós问题，这些问题是$ t $ tostersection和Erd \ h os-sows的解决方案。具体而言，我们表明，任何$ n $ element的排列集合集合，没有两个排列，最多与（确切的）$ t-1 $元素相交最多的$（n-t）！$，提供的$ t \ le n^{1- am^{1-ε} $（$ $ n> n_0（ε）$。这些问题的先前结果仅涉及固定$ t $的情况。证明遵循结构与随机性哲学，事实证明，在整个数学和计算机科学中证明结果非常有效。
We develop a new approach to approximate families of sets, complementing the existing `$Δ$-system method' and `junta approximations method'. The approach, which we refer to as `spread approximations method', is based on the notion of $r$-spread families and builds on the recent breakthrough result of Alweiss, Lovett, Wu and Zhang for the Erd\H os--Rado `Sunflower Conjecture'. Our approach can work in a variety of sparse settings. To demonstrate the versatility and strength of the approach, we present several of its applications to forbidden intersection problems, including bounds on the size of regular intersecting families, the resolution of the Erd\H os--Sós problem for sets in a new range and, most notably, the resolution of the $t$-intersection and Erd\H os--Sós problems for permutations in a new range. Specifically, we show that any collection of permutations of an $n$-element set with no two permutations intersecting in at most (exactly) $t-1$ elements has size at most $(n-t)!$, provided $t\le n^{1-ε}$ ($t \le n^{\frac{1}{3}-ε}$) for an arbitrary $ε>0$ and $n>n_0(ε)$. Previous results for these problems only dealt with the case of fixed $t$. The proof follows the structure vs. randomness philosophy, which proved to be very efficient in proving results throughout mathematics and computer science.
