2022
Lower bound on the size of a quasirandom forcing set of permutations
KUREČKA, MartinBasic information
Original name
Lower bound on the size of a quasirandom forcing set of permutations
Authors
KUREČKA, Martin (203 Czech Republic, guarantor, belonging to the institution)
Edition
COMBINATORICS PROBABILITY & COMPUTING, 2022, 0963-5483
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United Kingdom of Great Britain and Northern Ireland
Confidentiality degree
is not subject to a state or trade secret
References:
Impact factor
Impact factor: 0.900
RIV identification code
RIV/00216224:14330/22:00125023
Organization unit
Faculty of Informatics
UT WoS
000752712800001
EID Scopus
2-s2.0-85111434334
Keywords in English
quasirandomness; quasirandom permutations; combinatorial limits; quasirandomness forcing
Tags
International impact, Reviewed
Changed: 27/3/2023 17:06, RNDr. Pavel Šmerk, Ph.D.
Abstract
In the original language
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.
Links
| MUNI/A/1108/2020, interní kód MU |
| ||
| MUNI/A/1145/2021, interní kód MU |
| ||
| MUNI/A/1549/2020, interní kód MU |
| ||
| MUNI/I/1677/2018, interní kód MU |
|