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/22 edge flips and we show (n/22)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 socalled 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 (n3)edge connectedness
for all P in general position and (n3)vertex connectedness for
n large enough ((n3) is tight, since there is always a partial
triangulation which allows exactly n3 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.
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ó.
