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

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KUREČKA Martin

Rok publikování 2022
Druh Článek v odborném periodiku
Časopis / Zdroj COMBINATORICS PROBABILITY & COMPUTING
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://dx.doi.org/10.1017/S0963548321000298
Doi http://dx.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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.