On tree width, bramble size, and expansion

A bramble in a graph G is a family of connected subgraphs of G Such that any two of these subgraphs have a nonempty intersection or are joined by an edge. The order of a bramble is the least number of vertices required to cover every subgraph in the bramble. Seymour and Thomas [P.. Seymour, R. Thomas, Graph searching and a min-max theorem for tree-width, J. Combin. Theory Set. B 58 (1993) 22-33] proved that the maximum order of a bramble in a graph is precisely the tree width of the graph plus one. We prove that every graph of tree width at least k has a bramble of order Omega(k(1/2)/log(2)k) and size polynomial in n and k, and that for every k there is a graph G of tree width Omega(k) Such that every bramble of G of order k(1/2+epsilon) has size exponential in it. To prove the lower bound, we establish a close connection between linear tree width and vertex expansion. For the Upper bound, we use the connections between tree width, separators, and concurrent flows. (C) 2008 Elsevier Inc. All rights reserved.