Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, May 19, 2008

Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005

Lecture - 14:15

Bernd Gärtner - ETH Zürich

Regular Unique Sink Orientations

A unique sink orientation (USO) is an orientation of the n-cube graph with the property that every subgraph induced by a nonempty cube face has a unique sink. In particular, there is a unique global sink. In the talk, I will first discuss USO in general: Where do they come from? What are their combinatorial properties? Where are the algorithmic challenges?

In a second part, I will concentrate on specific families of USO. A family of USO is called regular if it can be described in a well-defined sense by a finite state transducer (nondeterministic finite automaton with output). Inituitively, this means that the family has a succint representation. To illustrate the concept, I will show that two well-known families of USO (by Klee & Minty, and by Morris) are regular.

In the last part, I will discuss the question whether families of USO with a succint representation in the above sense are from an algorithmic point of view "easier" than general families. I provide some partial answers and conclude with a number of open questions.

Colloquium - 16:00

Felix Breuer - FU Berlin

Uneven Splitting of Ham Sandwiches

The Ham Sandwich Theorem states that any n continuous measures in n-space can be split evenly with a single plane cut. More precisely: given n continuous measures m_1,...,m_n in n-space, there exists an affine hyperplane H that splits n-space into half-spaces H^+ and H^- such that m_i(H^+)=1/2 for all i. If we replace 1/2 with some other ratio, there exist continuous measures that cannot be split accordingly. Can we nonetheless make some useful statement about when an uneven splitting, i.e. a splitting according to some other fixed ratio, is possible? This is the question we will discuss in this talk.

Letzte Aktualisierung: 05.05.2008