# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# 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

### 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

### 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