The Library
Characterization of quasirandom permutations by a pattern sum
Tools
Tools
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
|
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 > 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 | |||||||||||||||
| Publisher Statement: | 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 | |||||||||||||||
| 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
