Monday, May 19, 2008
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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.