Department of
Applied
Mathematics

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.