Lectures and Colloquia during the semester

**January 28, 2002**

Freie Universität Berlin - Institut für
Informatik

Takustraße 9, 14195 Berlin

Room 005
- map -

**Lecture - 14:15**

### Martin Aigner - Freie Universität Berlin

### Square Ice

In how many ways can *n^2* water molecules be arranged in an *n x n*--block? This famous problem was solved a few years ago by
Kuperberg and Zeilberger. I will survey (with some shortcuts) the
main parts of the proofs:

Introduction: A wild conjecture

Theme 1: Combinatorics

Theme 2: Statistical Mechanics

Theme 3: Discrete Calculus

Finale: Putting it all together.

**Colloquium - 16:00**

### Martin Kutz - Freie Universität Berlin

### Treeifying Posets with Incomparability Constraints

*Abstract: *
We present an algorithm that extends a poset to a tree
satisfying given incomparability constraints.
This problem is closely related to tree description languages,
which are an important tool in computational linguistics.

More specifically, we are given a poset *(X,q)* together
with a collection *D* of incomparable pairs in *X*.
The task is to find an extension *q'* of the order *q*
so that the covering relations of *q'* form a rooted tree
while all pairs in *D* remain incomparable in *q'*.

Our algorithm solves this problem in time
*O(#X (m + #D))*,
where *m* is the size of the
- possibly sparse -
representation of the order *q*.

[home] -
[up] -
[top]