Publication details

Lower bound on the size of a quasirandom forcing set of permutations

Authors

KUREČKA Martin

Year of publication 2021
Type Article in Periodical
Magazine / Source COMBINATORICS PROBABILITY & COMPUTING
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.

More info