Lower bound on the size of a quasirandom forcing set of permutations
| Authors | |
|---|---|
| Year of publication | 2022 |
| Type | Article in Periodical |
| Magazine / Source | COMBINATORICS PROBABILITY & COMPUTING |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1017/S0963548321000298 |
| Doi | http://dx.doi.org/10.1017/S0963548321000298 |
| Keywords | quasirandomness; quasirandom permutations; combinatorial limits; quasirandomness forcing |
| Description | 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. |
| Related projects: |