Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Star transposition Gray codes for multiset permutations

Tools
- Tools
+ Tools

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)

[img]
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
Official URL: https://doi.org/10.4230/LIPIcs.CVIT.2016.23

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:
DateEvent
2022Published
19 December 2021Accepted
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 IDRIOXX Funder NameFunder ID
GA 19-08554SGrantová Agentura České Republikyhttp://dx.doi.org/10.13039/501100001824
413902284Deutsche Forschungsgemeinschafthttp://dx.doi.org/10.13039/501100001659
2019-72200522ANID 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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us