The Library
Characterization of quasirandom permutations by a pattern sum
Tools
Chan, T., Králʼ, Daniel, Noel, Jonathan A., Pehova, Yanitsa, Sharifzadeh, Maryam and Volec, Jan (2020) Characterization of quasirandom permutations by a pattern sum. Random Structures and Algorithms, 57 (4). pp. 920-939. doi:10.1002/rsa.20956 ISSN 1042-9832.
|
PDF
WRAP-characterization-quasirandom-permutations-pattern-sum-Kral-2020.pdf - Accepted Version - Requires a PDF viewer. Download (772Kb) | Preview |
Official URL: https://doi.org/10.1002/rsa.20956
Abstract
It is known that a sequence urn:x-wiley:rsa:media:rsa20956:rsa20956-math-0001 of permutations is quasirandom if and only if the pattern density of every 4‐point permutation in urn:x-wiley:rsa:media:rsa20956:rsa20956-math-0002 converges to 1/24. We show that there is a set S of 4‐point permutations such that the sum of the pattern densities of the permutations from S in the permutations urn:x-wiley:rsa:media:rsa20956:rsa20956-math-0003 converges to urn:x-wiley:rsa:media:rsa20956:rsa20956-math-0004 if and only if the sequence is quasirandom. Moreover, we are able to completely characterize the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Permutation groups, Random number generators, Combinatorial analysis | |||||||||||||||
Journal or Publication Title: | Random Structures and Algorithms | |||||||||||||||
Publisher: | John Wiley & Sons, Inc. | |||||||||||||||
ISSN: | 1042-9832 | |||||||||||||||
Official Date: | December 2020 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 57 | |||||||||||||||
Number: | 4 | |||||||||||||||
Page Range: | pp. 920-939 | |||||||||||||||
DOI: | 10.1002/rsa.20956 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | This is the peer reviewed version of the following article: Chan, TFN, Král', D, Noel, JA, Pehova, Y, Sharifzadeh, M, Volec, J. Characterization of quasirandom permutations by a pattern sum. Random Struct Alg. 2020; 1– 20. https://doi.org/10.1002/rsa.20956, which has been published in final form at https://doi.org/10.1002/rsa.20956. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 6 July 2020 | |||||||||||||||
Date of first compliant Open Access: | 27 August 2021 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year