#
Monday Lecture and Colloquium

**Monday, May 12, 2014**

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

### Christian Krattenthaler -
Universität Wien

### A dual of MacMahon's theorem on plane partitions

*Abstract:*

Plane partitions are fascinating combinatorial objects which
were introduced by Percy Alexander MacMahon around 1900. After
MacMahon's work, they got more or less forgotten, until in the
late 1960s and early 1970s interest arose again, mainly
instigated by an open conjecture of MacMahon. Over the past 40
years, investigation has been one of the central subjects of
enumerative combinatorics.

It came as a revelation around 1990, when it was realised that
plane partitions can be alternatively viewed as rhombus tilings
of a hexagon. In this sense, the classical theorem of MacMahon
alluded to in the title states that the number of rhombus
tilings of any centrally symmetric hexagon drawn on the triangular
lattice is given by a beautifully simple product formula.
I shall present a kind of "dual" of this formula, which is in fact
a limit relation between the "numbers" of rhombus tilings of
infinite regions. The "actual" main theorem behind is a closed
product formula for the number of rhombus tilings of a hexagon
with a hole in its interior which has the form of four adjacent
triangles.

I shall use this talk to give a flavour of what the enumeration
of rhombus tilings is about, and how theorems can be proven in
this area.

This is joint work with Mihai Ciucu.

** Colloquium - 16:00**

### Yannik Stein -
Freie Universität Berlin

### The Complexity of the Nearest Colorful Polytope Problem

*Abstract:*

Let P_1,...,P_{d+1} be point sets in R^d whose convex hulls
each contain the origin. Each set represents a color class.

The Colorful Caratheodory theorem guarantees the existence of a colorful choice, i.e., a set that contains exactly one point from each color class, whose convex hull also contains the origin. The computational complexity of finding such a colorful choice is still unknown. We study a natural generalization of the problem: in the Nearest Colorful Polytope problem (NCP), we are given n sets
P_1,...,P_n in R^d and we would like to find a colorful choice whose convex hull minimizes the distance to the origin. We show that computing local optima of the NCP problem is PLS-complete, while computing a global optimum is NP-hard.

Joint work with Wolfgang Mulzer.

Letzte Aktualisierung:
06.05.2014