You are cordially invited to our next Monday Lecture &
Colloquium on April 29th at 14:15 h & 16:00 h at TU Berlin.
Location: Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, April 29th  14:15 h Lecture: Kolja Knauer (AixMarseille Université) Title: Tope graphs of (Complexes of) Oriented
Matroids Tope graphs of Complexes of Oriented Matroids fall into the important class of metric graphs called partial cubes. They capture a variety of interesting graphs such as flip graphs of acyclic orientations of a graph, linear extension graphs of a poset, region graphs of hyperplane arrangements to name a few. After a soft introduction into oriented matroids and tope graphs, we give two purely graph theoretical characterizations of tope graphs of Complexes of Oriented Matroids. The first is in terms of a new notion of excluded minors for partial cube, the second is in terms of classical metric properties of certain socalled antipodal subgraphs. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we give a polynomial time recognition algorithms for tope graphs, which solves a relatively long standing open question. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory. Based on
joint work with H.J; Bandelt, V. Chepoi, and T. Marc.
Coffee & Tea Break : Room MA 316  Third Floor [British Reading] Time: Monday, April 29th  16:00 h s.t. Colloquium: Torsten Mütze (Technische Universität Berlin) Title: Combinatorial generation via permutation
languages In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the SteinhausJohnsonTrotter algorithm to generate all permutations of an nelement set by adjacent transpositions; the binary reflected Gray code to generate all nbit strings by flipping a single bit in each step; the Gray code for generating all nvertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an nelement ground set by element exchanges due to Kaye. The first main application of our framework are permutation patterns, yielding new Gray codes for different patternavoiding permutations, such as vexillary, skewmerged, Xshaped, separable, Baxter and twisted Baxter permutations etc. We also obtain new Gray codes for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to different restrictions. The second main application of our framework are lattice congruences of the weak order on the symmetric group S_n. Recently, Pilaud and Santos realized all those lattice congruences as (n1)dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian. This is joint work with
Liz Hartung, Hung P. Hoang, and Aaron Williams.
