[home] - [up]


Lectures and Colloquia during the semester



May 24, 2004

Humboldt-Universität zu Berlin
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV           - map -
Lecture - 14.00 Uhr c.t.

Gilles Schaeffer - Laboratoire d'informatique de l'École polytechnique, Palaiseau

Coding, counting and sampling triangulations and other planar graphs

Abstract: This talk will revolve around a combinatorial result: Three-connected planar graphs with n edges are "essentially" in bijection with unrooted binary trees with n nodes.

As a consequence the number of these graphs is related to the Catalan numbers. Moreover a 3-connected graph with n edges can be encoded by a parenthesis sequence of 2n bits, matching the information theoretic bound of 2 bits per edge. In particular this shows that, at least for spherical topology, traversal based algorithms can encode the connectivity of polyhedral meshes optimally in the worst case.

The above bijection is one in a series of results that build on properties of minimal alpha-orientations to explain remarkable counting formulas for standard families of planar graphs and maps. The striking similarities of these constructions call for a general theory which is still missing...

The talk is based in parts on recent results by Eric Fusy, Dominique Poulalhon and the speaker.


Colloquium - 16 Uhr s.t.

Martin Kutz -Freie Universität Berlin

Small Improvements on Conway's Angel Problem

Abstract: Two players, the angel and the devil, play a game on an infinite chess board. In each move the devil blocks an arbitrary square of the board such that it may no longer be stepped upon by the angel. The angel in turn, flies in each move from his current position to some unblocked location at distance at most k for some fixed integer k. Note that unlike the angel, the devil is not a figure on the board but just an entity that manipulates the board. Its moves are not restricted to the angel's proximity or limited by any other distance bounds; he can pick squares at completely arbitrary locations.

The devil wins if he can strand the angel, i.e., if he manages to get him into a position with all squares in the 2k+1 by 2k+1 area around him blocked. The angel wins simply if he succeeds to fly on forever. The open question is, whether for some sufficiently large integer k the angel with power k, called the k-angel, can win this game. This problem was introduced in Berlekamp, Conway, and Guy's classic "Winning Ways" (1982) and later investigated in greater depth by Conway (1996).

We present minor advances on the current best known devil strategy. For our improvement we first need to introduce a reformulation of the game in order to be able to state our result. The main point about our approach is that it emphasizes the important aspect of the game: speed, which might be a key to understanding the general question whether some angel can escape. We also treat the higher-dimensional analog of the angel game, showing that an angel of sufficiently large power can escape in 3D.


[home] - [up] - [top]