Star transposition Gray codes for multiset permutations

DOI10.1002/JGT.22915zbMATH Open1522.05006arXiv2108.07465OpenAlexW3194551264MaRDI QIDQ6074576FDOQ6074576

Authors: Petr Gregor, Arturo I. Merino, Torsten Mütze 

Publication date: 12 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Given integers $kgeq2$ and $a_1,ldots,a_{k}geq1$, let $$ and $n:=a_1+cdots+a_k$. An $$-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 $$-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 $$ that allows us to distinguish three different regimes for this problem. We show that if $$, then a star transposition Gray code for $$-multiset permutations does not exist. We also construct such Gray codes for the case $$, assuming that they exist for the case $$. For the case $$ 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.

Full work available at URL: https://arxiv.org/abs/2108.07465

Recommendations

• Gray code for permutations with a fixed number of cycles
• Trimming and gluing Gray codes
• Trimming and gluing Gray codes
• Combinatorial generation via permutation languages. I: Fundamentals
• A Gray code for the shelling types of the boundary of a hypercube

zbMATH Keywords

combinationpermutationGray codeHamilton cycletransposition

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner
• A method and two algorithms on the theory of partitions
• An algorithm for generating subsets of fixed size with a strong minimal change property
• The greedy Gray code algorithm
• Greedy flipping of pancakes and burnt pancakes
• Some Hamilton Paths and a Minimal Change Algorithm
• Title not available (Why is that?)
• A Survey of Combinatorial Gray Codes
• Title not available (Why is that?)
• Generation of Permutations by Adjacent Transposition
• A new algorithm for generation of permutations
• Hamiltonian-laceability of star graphs
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamilton-connected Cayley graphs on Hamiltonian groups
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gray codes with restricted density
• Explicit matchings in the middle levels of the Boolean lattice
• The coolest way to generate combinations
• Adjacent interchange generation of combinations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proof of the middle levels conjecture
• Title not available (Why is that?)
• Doubly adjacent gray codes for the symmetric group
• Distance-2 Cyclic Chaining of Constant-Weight Codes
• Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
• A short proof of the middle levels theorem
• A constant-time algorithm for middle levels Gray codes
• A Hamilton cycle in the \(k\)-sided pancake network
• Solving the sigma-tau problem

This page was built for publication: Star transposition Gray codes for multiset permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074576)