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

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KUREČKA Martin

Year of publication 2022
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.