Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

Can you get drunk on unique sink orientations?

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² 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