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