BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In this talk I present a general and versatile algorithmic fra
 mework for exhaustively generating a large variety of different combinatori
 al objects\, based on encoding them as permutations\, which provides a unif
 ied view on many known results and allows us to prove many new ones. In par
 ticular\, we obtain the following four classical Gray codes as special case
 s: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of 
 an n-element set by adjacent transpositions\; the binary reflected Gray cod
 e to generate all n-bit strings by flipping a single bit in each step\; the
  Gray code for generating all n-vertex binary trees by rotations due to Luc
 as\, van Baronaigien\, and Ruskey\; the Gray code for generating all partit
 ions of an n-element ground set by element exchanges due to Kaye. The first
  main application of our framework are permutation patterns\, yielding new 
 Gray codes for different pattern-avoiding permutations\, such as vexillary\
 , skew-merged\, X-shaped\, separable\, Baxter and twisted Baxter permutatio
 ns etc. We also obtain new Gray codes for five different types of geometric
  rectangulations\, also known as floorplans\, which are divisions of a squa
 re into n rectangles subject to different restrictions. The second main app
 lication of our framework are lattice congruences of the weak order on the 
 symmetric group S_n. Recently\, Pilaud and Santos realized all those lattic
 e congruences as (n-1)-dimensional polytopes\, called quotientopes\, which 
 generalize hypercubes\, associahedra\, permutahedra etc. Our algorithm gene
 rates each of those lattice congruences\, by producing a Hamilton path on t
 he skeleton of the corresponding quotientope\, yielding a constructive proo
 f that each of these highly symmetric graphs is Hamiltonian.   This is join
 t work with Liz Hartung\, Hung P. Hoang\, and Aaron Williams. 
DTSTAMP:20190417T153800
DTSTART:20190429T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
 es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Torsten Mütze (Technische Universität Berlin): Combinatorial genera
 tion via permutation languages
UID:95690565@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190429-C-Muetze.html
END:VEVENT
END:VCALENDAR