Dear all,
This is a reminder that we have a noon lecture today at 12:20. Please find the talk details below.
Best regards, Misha.
--------------------------------------------------------------
Star transposition Gray codes for multiset permutations Torsten Mütze University of Warwick and Charles University May 24, 2022, 12:20 in S6
Abstract 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 \Delta(a):=n-2*max {a_1,...,a_k} that allows us to distinguish three different regimes for this problem. We show that if \Delta(a)<0, then a star transposition Gray code for a-multiset permutations does not exist. We also construct such Gray codes for the case \Delta(a)>0, assuming that they exist for the case \Delta(a)=0. For the case \Delta(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.
This is joint work with Petr Gregor and Arturo Merino
--------------------------------------------------------------
On 2022-05-23 13:27, Mykhaylo Tyomkyn wrote:
Dear all,
This week we have *two* noon lectures, on Tuesday and Thursday:
Torsten Mütze (University of Warwick and Charles University): Star transposition Gray codes for multiset permutations. May 24, 2022, 12:20 in S6.
Arturo Merino (TU Berlin): Greedily generating all bases of a matroid by base exchanges. May 26, 2022, 12:20 in S6.
Please find the abstracts on the webpage https://www.mff.cuni.cz/en/kam/teaching-and-seminars/noon-lectures
I will send out reminders on the days of the talks.
Best regards, Misha Tyomkyn. _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz