Star transposition Gray codes for multiset permutations

DOI10.1002/JGT.22915zbMATH Open1522.05006OpenAlexW3194551264MaRDI 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)

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

zbMATH Keywords

combinationpermutationGray codeHamilton cycletransposition

Mathematics Subject Classification ID

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

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.

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

Cites Work

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

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)