J 2022

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

KUREČKA, Martin

Základní údaje

Originální název

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

Autoři

KUREČKA, Martin (203 Česká republika, garant, domácí)

Vydání

COMBINATORICS PROBABILITY & COMPUTING, 2022, 0963-5483

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Velká Británie a Severní Irsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 0.900

Kód RIV

RIV/00216224:14330/22:00125023

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000752712800001

Klíčová slova anglicky

quasirandomness; quasirandom permutations; combinatorial limits; quasirandomness forcing

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 27. 3. 2023 17:06, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

MUNI/A/1108/2020, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Akronym: SV-FI MAV X.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X.
MUNI/A/1145/2021, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Akronym: SV-FI MAV XI.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.
MUNI/A/1549/2020, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21
MUNI/I/1677/2018, interní kód MU
Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)
Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities