| [home] - [up] |
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
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.