Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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
*n*^{2} 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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login