The Library
Star transposition Gray codes for multiset permutations
Tools
Gregor, Petr, Merino, Arturo and Mutze, Torsten (2023) Star transposition Gray codes for multiset permutations. Journal of Graph Theory, 103 (2). pp. 212-270. doi:10.1002/jgt.22915 ISSN 0364-9024.
|
PDF
WRAP-Star-transposition-Gray-codes-for-multiset-permutations-Mutze-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (4Mb) | Preview |
Official URL: https://doi.org/10.1002/jgt.22915
Abstract
Given integers k≥2 and a1,…,ak≥1, let a≔(a1,…,ak) and n≔a1+⋯+ak. An a-multiset permutation is a string of length n that contains exactly ai symbols i for each i=1,…,k. In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, that is, in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results. For example, it is known that permutations (a1=⋯=ak=1) can be generated by star transpositions, while combinations (k=2) can be generated by these operations if and only if they are balanced (a1=a2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter Δ(a)≔n−2max{a1,…,ak} that allows us to distinguish three different regimes for this problem. We show that if Δ(a)<0, then a star transposition Gray code for a-multiset permutations does not exist. We also construct such Gray codes for the case Δ(a)>0, assuming that they exist for the case Δ(a)=0. For the case Δ(a)=0 we present some partial positive results. Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Combinations, Permutations, Gray codes | |||||||||
Journal or Publication Title: | Journal of Graph Theory | |||||||||
Publisher: | John Wiley & Sons Ltd. | |||||||||
ISSN: | 0364-9024 | |||||||||
Official Date: | June 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 103 | |||||||||
Number: | 2 | |||||||||
Page Range: | pp. 212-270 | |||||||||
DOI: | 10.1002/jgt.22915 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 8 December 2022 | |||||||||
Date of first compliant Open Access: | 10 January 2023 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Related URLs: | ||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year