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 (Aix-Marseille 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 so-called 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.

**R****oom MA 316 - Third Floor**** [British
Reading] **

__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 Steinhaus-Johnson-Trotter algorithm to generate all permutations of an n-element set by adjacent transpositions; the binary reflected Gray code 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 Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions 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 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 (n-1)-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.

--------------F45305BC7659D95BC2B101B9--
From i.brunke@inf.fu-berlin.de Tue Apr 30 13:11:11 2019
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
by list1.zedat.fu-berlin.de (Exim 4.85)
for facets-of-complexity@lists.fu-berlin.de with esmtps
(TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256)
(envelope-from You are cordially invited to our next Monday Lecture &
Colloquium on May 6th 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, May 6th - 14:15 h**

__Lecture__: Matthias Köppe (University of California)

__Title__: Facets of cut-generating functionology

In the theory of valid inequalities for integer point sets in polyhedra, the traditional, finite-dimensional techniques of polyhedral combinatorics are complemented by infinite-dimensional methods, the study of cut-generating functions. I will give an introduction to these methods and will explain their connection tolattice-free convex bodies. I will present recent results involving inverse semigroups of partial maps, obtained jointly with Robert Hildebrand and Yuan Zhou, and highlight some open questions regarding computability and complexity.

**R****oom MA 316 - Third Floor**** [British
Reading] **

__Colloquium__: Tillmann Miltzow (Universität Utrecht**)**

__Title__: Smoothed Analysis of the Art Gallery Problem

In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation.Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude \delta of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ER-complete problem was analyzed by Smoothed Analysis.

This is joint work with
Michael Dobbins and Andreas Holmsen.

--------------A620DCED0A2FE03E72D88A04--
From i.brunke@inf.fu-berlin.de Fri May 10 13:45:23 2019
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
by list1.zedat.fu-berlin.de (Exim 4.85)
for facets-of-complexity@lists.fu-berlin.de with esmtps
(TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256)
(envelope-from You are cordially invited to our next Monday Lecture &
Colloquium on May 13th 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, May 13th - 14:15 h**

__Lecture__: Boaz Slomka (Weizmann Institute of
Science, Rehovot Israel)

__Title__: On Hadwiger's covering conjecture

A
long-standing open problem, known as Hadwiger’s covering
problem, asks what is the smallest natural number N(n) such
that every convex body in {\mathbb R}^n can be covered by a
union of the interiors of at most N(n) of its translates.

In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a new general upper bound for N(n).

In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a new general upper bound for N(n).

**R****oom MA 316 - Third Floor**** [British
Reading] **

__Colloquium__: Fei Xue (Technische Universität Berlin**)**

__Title__: On the lattice point covering problem in
dimension 2

We say that a convex body K has the lattice point covering property, if K contains a lattice point of Z^n in any position, i.e., in any translation and rotation of K. In this talk we discuss the lattice point covering property of some regular polygons in dimension 2.

You are cordially invited to our next Monday Lecture &
Colloquium on May 27th 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, May 27th - 14:15 h**

__Lecture__: William T. Trotter (Georgia Institute of
Technology)

__Title__: Stability Analysis for Posets

Trivially, the
maximum chromatic number of a graph on n vertices is n, and the
only graph which achieves this value is the complete graph K_n.
It is natural to ask whether this result is "stable", i.e., if n
is large, G has n vertices and the chromatic number of G is close
to n, must G be close to being a complete graph? It is easy to
see that for each c>0, if G has n vertices and chromatic
number at least n−c, then it contains a clique whose size is at
least n−2c. We will consider the analogous questions for posets
and dimension. Now the discussion will really become interesting.

**R****oom MA 316 - Third Floor**** [British Reading]
**

__Colloquium__: Felix Schröder (Technische Universität
Berlin**)**

__Title__: Lower Bounds on the p-centered coloring number

A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity. We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number is in Theta(p log p). We have examples of graphs of treewidth k needing (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz. We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz.

--------------F67A313D5F06BB1B277B7077-- From newman.534@buckeyemail.osu.edu Fri May 31 15:18:28 2019 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-fromDear Facets of Complexity member= s,

Next week, the International Con=
ference on Network Games, Tropical Geometry and Quantum Communication will =
be taking place from Monday to Friday at the Zuse Institute Berlin. More in=
formation can be found at
https://www3.math.tu-berlin.de/combi/dmg/TES-Summer2019/conference.html=
. All are invited to participate. Due to the conference, the regular =
Facets of Complexity Monday Lectures will not take place.

Best regards,

AndrewYou are cordially invited to our next Monday Lecture on June 17th
at 14:15 h at FU Berlin.

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, June 17th - 14:15 h**

__Lecture__: Matthias Beck (San Francisco State University**)**

__Title__: Lonely Runner Polyhedra

We study the Lonely Runner Conjecture, conceived by Wills in the 1960's: Given positive integers n_1, n_2, ..., n_k, there exists a positive real number t such that for all 1 ≤ j ≤ k the distance of tn_j to the nearest integer is at least 1/(k+1). Continuing a view-obstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral ansatz to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture.

--------------73E0E384B595583E0FC6ECB6-- From i.brunke@inf.fu-berlin.de Wed Jun 19 15:54:36 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from

You are cordially invited to our next Monday Lecture &
Colloquium on June 24th at 14:15 h & 16:00 h at FU Berlin.

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, June 24th - 14:15 h**

__Lecture__: Emo Welzl (ETH Zürich**)**

__Title__: Connectivity of Triangulation Flip Graphs in the
Plane

In a straight line embedded triangulation of a point set P in
the plane, removing an inner edge and - provided the resulting
quadrilateral Q is convex - adding the other diagonal is called
an edge flip. The flip graph has all triangulations as vertices
and a pair of triangulations is adjacent, if they can be
obtained from each other by an edge flip. This presentation is
towards a better understanding of this graph, with emphasis on
its connectivity. It is known that every triangulation allows at
least n/2-2 edge flips and we show (n/2-2)-vertex connectivity
for flip graphs of all P in general position, n:=|P|. Somewhat
stronger, but restricted to P large enough, we show that the
vertex connectivity is determined by the minimum degree
occurring in the flip graph, i.e. the minimum number of
flippable edges in any triangulation of P. A corresponding
result is shown for so-called partial triangulations, i.e. the
set of all triangulations of subsets of P which contain all
extreme points of P. Here the flip operation is extended to
bistellar flips (edge flip, and insertion and removal of an
inner vertex of degree three). We prove (n-3)-edge connectedness
for all P in general position and (n-3)-vertex connectedness for
n large enough ((n-3) is tight, since there is always a partial
triangulation which allows exactly n-3 bistellar flips). This
matches the situation known (through the secondary polytope) for
regular triangulations (i.e. partial triangulations obtained by
lifting the points and projecting the lower convex hull). This
is joint work with Uli Wagner, IST Austria.

**Coffee & Tea Break****:**

**Room 134**

__Time__: **Monday, ****June 24th**** -
16:00 h s.t.**

__Colloquium__: Simona Boyadzhiyska (Freie Universität
Berlin**)**

__Title__: On counting problems related to (mutually)
orthogonal Latin squares

An n×n array with
entries in [n] such that each integer appears exactly once in
every row and every column is called a Latin square of order n.
Two Latin squares L and L' are said to be orthogonal if, for all
x,y∈[n], there is a unique pair (i,j) such that L(i,j) = x and
L'(i,j) = y; k Latin squares are mutually orthogonal if any two of
them are orthogonal.After the question of existence of a
combinatorial structure satisfying given properties, a natural and
important problem is to determine how many such objects there are.
In this talk, we will consider some counting questions related to
(mutually) orthogonal Latin squares. We will present an upper
bound on the number of ways to extend a set of k mutually
orthogonal Latin squares to a set of k+1 mutually orthogonal Latin
squares and discuss some applications, comparing the resulting
bounds to previously known lower and upper bounds.This talk is
based on joint work with Shagnik Das and Tibor Szabó.