L3 | Mathematical Institute

Tue, 20 May 2008
14:30

"Turan/Erdos-Stone type problems involving coloured graphs"

Ed Marchant

(Cambridge)

Abstract

Let G be the union of a red graph R and a blue graph B where every edge of G is in R or B (or both R and B). We call such a graph 2-painted. Given 2-painted graphs G and H, we say that G contains a copy of H if we can find a subgraph of G which is isomorphic to H. Let 0

Tue, 06 May 2008
14:30

Overhang Bounds

Mike Paterson

(Warwick)

Abstract

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n.

Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^{1/3}, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^{1/3} is best possible, resolving the long-standing overhang problem up to a constant factor.

I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years.