Combinatorics Seminar
When: Sunday, March 18, 10am
Where: Schreiber 309
Speaker: Uri Zwick, Tel Aviv University
Title: Overhang
Abstract:
How far off the edge of the table can we reach by stacking n
identical, homogeneous, frictionless blocks of length 1? A classical
solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+..+1/n
is the n-th harmonic number. This solution is widely believed to be
optimal. Paterson and Zwick have recently shown, however, that this
solution is exponentially far from being optimal by constructing simple
n-block stacks that achieve an overhang of cn^{1/3}, for some constant
c>0. We show that larger overhangs are impossible.
Joint work with Mike Paterson, Yuval Peres, Mikkel Thorup and
Peter Winkler.