License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.34
URN: urn:nbn:de:0030-drops-158448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15844/
Go to the corresponding LIPIcs Volume Portal

Gregor, Petr ; Mütze, Torsten ; Merino, Arturo

Star Transposition Gray Codes for Multiset Permutations

pdf-format:
LIPIcs-STACS-2022-34.pdf (2 MB)

Abstract

Given integers k ≥ 2 and a_1,…,a_k ≥ 1, let a: = (a_1,…,a_k) and n: = a_1+⋯+a_k. An a-multiset permutation is a string of length n that contains exactly a_i symbols i for each i = 1,…,k. In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, i.e., 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 (a_1 = ⋯ = a_k = 1) can be generated by star transpositions, while combinations (k = 2) can be generated by these operations if and only if they are balanced (a_1 = a_2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter Δ(a): = n-2max{a_1,…,a_k} 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.

BibTeX - Entry

@InProceedings{gregor_et_al:LIPIcs.STACS.2022.34,
  author =	{Gregor, Petr and M\"{u}tze, Torsten and Merino, Arturo},
  title =	{{Star Transposition Gray Codes for Multiset Permutations}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15844},
  URN =		{urn:nbn:de:0030-drops-158448},
  doi =		{10.4230/LIPIcs.STACS.2022.34},
  annote =	{Keywords: Gray code, permutation, combination, transposition, Hamilton cycle}
}

Keywords: Gray code, permutation, combination, transposition, Hamilton cycle
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI