论文标题
下限在Quasirandom强迫集合的尺寸上
Lower bound on the size of a quasirandom forcing set of permutations
论文作者
论文摘要
如果对于任何顺序$ \ {π_i\} _ {i \ in \ Mathbb {n}} $，其中密度$ d（π，π_i）$会收敛到$ \ frac {1} $ s $ s的$ s，则$ s $ s $的排列会强制强制。 $ \ {π_i\} _ {i \ in \ mathbb {n}} $是quasirandom。格雷厄姆（Graham）询问是否存在整数$ k $，以使所有订单$ k $的排列集都在强迫；对于任何$ k \ ge 4 $，这都是正确的。特别是，所有二十四个订单排列$ 4 $的集合都在强迫。我们在强迫集合集的大小上提供了第一个非平凡的下限：每条置换集集（带有任意订单）至少包含四个排列。
A set $S$ of permutations is forcing if for any sequence $\{Π_i\}_{i \in \mathbb{N}}$ of permutations where the density $d(π,Π_i)$ converges to $\frac{1}{|π|!}$ for every permutation $π\in S$, it holds that $\{Π_i\}_{i \in \mathbb{N}}$ is quasirandom. Graham asked whether there exists an integer $k$ such that the set of all permutations of order $k$ is forcing; this has been shown to be true for any $k\ge 4$. In particular, the set of all twenty-four permutations of order $4$ is forcing. We provide the first non-trivial lower bound on the size of a forcing set of permutations: every forcing set of permutations (with arbitrary orders) contains at least four permutations.
