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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři

KUREČKA Martin

Rok publikování 2021
Druh Článek v odborném periodiku
Časopis / Zdroj Combinatorics, Probability and 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.

Další info