Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 19, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Bernd Gärtner
Let's recall a classic problem from theoretical computer science: A drunkard is walking along a street that is n meters wide. Starting in the middle of the street and randomly staggering half a meter to the left or to the right with every step, how long does it take until the drunkard ends up in the ditch? The precise answer will be given in the talk, but the rough answer is: asymptotically n2 steps on average.
Now imagine that the drunkard is staggering on the graph of the n-dimensional cube. All cube edges are oriented, and each step takes the drunkard from its current position (a vertex) to a neighboring vertex randomly chosen among the ones that are reachable through an outgoing edge.
Not that the drunkard cares much, but the orientation is in fact a unique sink orientation (USO). This means that any subcube (in particular the whole cube) induces a subgraph with exactly one sink (vertex with no outgoing edge). The global sink now plays the role of the ditch, and again we ask how many steps it takes the drunkard to end up in the ditch. An easy consequence of the USO property is that from every vertex, there is a directed path of length at most n to the global sink: like in the original problem, the ditch is never more than n steps away.
Here is what we will show (and this is a result of Walter Morris): there exists a (drinker-friendly) unique sink orientation of the n-cube on which the drunkard will take exponentially many steps before ending up in the ditch.
If time permits, we will also elaborate on the relevance of this result outside the world of drunkards.
Automatic MiSe System Software Version 1.4803M | admin login