Gregor, Petr, Mutze, Torsten and Merino, Arturo (2022) Star transposition Gray codes for multiset permutations. In: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Marseille, 15-18 Mar 2022. Published in: Proceedings of STACS 2022 doi:10.4230/LIPIcs.CVIT.2016.23 (In Press)

Preview

PDF WRAP-Star-transposition-Gray-codes-multiset-permutations-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (2309Kb) | Preview

Request Changes to record.

Abstract

Given integers $k\geq 2$ and $a_1,\ldots,a_k\geq 1$, let $\ba:=(a_1,\ldots,a_k)$ and $n:=a_1+\cdots+a_k$.
An $\ba$-multiset permutation is a string of length~$n$ that contains exactly $a_i$ symbols~$i$ for each $i=1,\ldots,k$.
In this work we consider the problem of exhaustively generating all $\ba$-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=\cdots=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~$\Delta(\ba):=n-2\max\{a_1,\ldots,a_k\}$ that allows us to distinguish three different regimes for this problem.
We show that if $\Delta(\ba)<0$, then a star transposition Gray code for $\ba$-multiset permutations does not exist.
We also construct such Gray codes for the case $\Delta(\ba)>0$, assuming that they exist for the case~$\Delta(\ba)=0$.
For the case~$\Delta(\ba)=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:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Gray codes, Permutations , Combinations , Combinatorial analysis, Computer science -- Mathematics
Journal or Publication Title:	Proceedings of STACS 2022
Publisher:	LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Official Date:	2022
Dates:	Date Event 2022 Published 19 December 2021 Accepted
DOI:	10.4230/LIPIcs.CVIT.2016.23
Status:	Peer Reviewed
Publication Status:	In Press
Access rights to Published version:	Open Access
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID GA 19-08554S Grantová Agentura České Republiky http://dx.doi.org/10.13039/501100001824 413902284 Deutsche Forschungsgemeinschaft http://dx.doi.org/10.13039/501100001659 2019-72200522 ANID Becas Chile https://www.anid.cl/
Conference Paper Type:	Paper
Title of Event:	39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Type of Event:	Workshop
Location of Event:	Marseille
Date(s) of Event:	15-18 Mar 2022
Related URLs:	Organisation Publisher
Open Access Version:	https://arxiv.org/abs/2108.07465

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads