[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - June 24th 2019

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

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

Location:

Room 005 - Ground Floor
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

Abstract:

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

Abstract:

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ó.