#
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

*Abstract:*

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

*Abstract:*

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