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

KUREČKA, Martin. Lower bound on the size of a quasirandom forcing set of permutations. COMBINATORICS PROBABILITY & COMPUTING. 2022, vol. 31, No 2, p. 304-319. ISSN 0963-5483. Available from: https://dx.doi.org/10.1017/S0963548321000298.

Basic 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

• Original 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
• WWW: URL
• Impact factor: Impact factor: 0.900
• RIV identification code: RIV/00216224:14330/22:00125023
• Organization unit: Faculty of Informatics
• Doi: http://dx.doi.org/10.1017/S0963548321000298
• UT WoS: 000752712800001
• Keywords in English: quasirandomness; quasirandom permutations; combinatorial limits; quasirandomness forcing
• Tags: International impact, Reviewed

Abstract

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: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Acronym: SV-FI MAV X.)

Investor: Masaryk University

• MUNI/A/1145/2021, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Acronym: SV-FI MAV XI.)

Investor: Masaryk University

• MUNI/A/1549/2020, interní kód MU: Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Acronym: SKOMU)

Investor: Masaryk University

• MUNI/I/1677/2018, interní kód MU: Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities