Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 03.05.2007 at 13:00 in S5, there is the following noon lecture:

On tree width, bramble size, and expansion

Dániel Marx

Abstract

The notion of brambles gives a dual characterization of tree width: Seymour and Thomas proved that a graph has a tree decomposition of width k if and only if every bramble has order at most k+1. In this talk we investigate this notion and examine what happens if we would like to have brambles of polynomial size. We are able to show that every graph has a polynomial-size bramble whose order is roughly the square root of the tree width of the graph, but there are graphs where every bramble with order larger than the square root of the tree width has to be of exponential size.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010