Lower bound on the size of a quasirandom forcing set of permutations
| Autoři | |
|---|---|
| Rok publikování | 2022 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | COMBINATORICS PROBABILITY & COMPUTING |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1017/S0963548321000298 |
| Doi | https://doi.org/10.1017/S0963548321000298 |
| Klíčová slova | quasirandomness; quasirandom permutations; combinatorial limits; quasirandomness forcing |
| Popis | A set S of permutations is forcing if for any sequence {Pi_i} of permutations where the density d(pi, Pi_i) converges to 1/|pi|! for every permutation pi from S, it holds that {Pi_i} 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>=4 . In particular, the set of all 24 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. |
| Související projekty: |