2
$\begingroup$

I am looking for ideas how to solve the problem from Diestel's textbook Graph Theory.

Chapter 12. Minors, Trees, and WQO.

Problem 16. Apply Theorem 12.3.9 to show that the $k \times k$ grid has tree-width at least $k$, and find a tree-decomposition of width exactly $k$.

Theorem 12.3.9. (Seymour & Thomas 1993). Let $k \geq 0$ be an integer. A graph has tree-width $\geq k$ if and only if it contains a bramble of order $> k$. (A bramble is a set of mutually touching connected vertex sets in $G$; its order is the minimum number of vertices in a set meeting each member of the bramble.)

The problem is the proof of the theorem 12.3.9 was given in the terms of bramble, which is a bit confusing, at present I don't really see the way to solve the problem by using this theorem.

If you familiar with the topic, please, help me out.

Addendum:

In Graphs & Algorithms: Advanced Topics on the slide 5.

The $n\times n$ - grid on $\left \{(i,k) | 1 \leq i, j \leq n\right \}$ has treewidth $\leq n$: Consider the path on

$X_{n(i-1)+j}=\left \{(i,k)|j\leq k\leq n\right \}\cup\left \{(i+1,k)|1\leq k\leq j\right \}, 1\leq i\leq n-1, 1\leq j\leq n$

How this is supposed to help me?

  • 0
    The $X_{n(i-1)+j}$ are the vertex sets (Wagner’s *bags* in slide 3) in a tree decomposition of the $n\times n$ grid of treewidth $n$.2012-01-14

2 Answers 2

2

Here are a couple of big hints.

First, you need a bramble of order $k+1$. Let $G_k$ be the $k\times k$ grid, with vertices $\langle i,j\rangle$ for $1\le i,j\le k$. Thus, $G_{k-1}$ is the $(k-1)\times(k-1)$ grid in the upper lefthand corner of $G_k$. Start with the $(k-1)^2$ crosses in $G_{k-1}$; they form a bramble $\mathscr{B}$ of order $k-1$ for $G_{k-1}$. Of course these crosses don’t meet the bottom row and last column of $G_k$ at all. It’s possible to add just two sets to $\mathscr{B}$ to make a bramble of order $k+1$ for $G_k$. A good place to look for these sets is the part of $G_k$ that isn’t touched by $\mathscr{B}$ at all.

Then you need a tree decomposition of $G_k$ of width $k$. Uli Wagner’s slide 5 gives you one, though you still have to figure out the tree on which it’s based in order to prove that it is a tree decomposition. Note that he indexed the sets in the decomposition by consecutive integers; this is a big hint for the shape of the tree in question, and once you make the right guess, it isn’t hard to verify.

  • 0
    @com: I’d never heard of brambles and tree decompositions until I saw your question, so I’m not the best person to ask! However, from Lemma 12.3.5 you know that a clique has to belong to one part of a tree decomposition, so large cliques force large treewidth. A bramble is like a fat clique: just as all the vertices of a clique are connected by edges, all the sets in a bramble touch one another. To get a really good feel for what’s going on, though, I suspect that one has to get a feel for tree decompositions, and I’ve not played with them enough for that.2012-01-17
2

I didn't read Diestel's book, but simple observation may be help is, if $G$ is a grid then we know $\operatorname{tw}(G) \ge BN(G)-1$ and as you know if you select $row_i \cup col_j$ as a bramble set, its hitting set size is $n$, so treewidth is at least $n-1$. Also you can simply construct a tree decomposition with size of $n$. So treewidth is $n$ or $n-1$. (By $BN(G)$ I mean bramble number of $G$.)

Edit: As Braian mentioned you can simply find good brambles and answer of sample tree decomposition is in your question. (my mistake was I thinking about $cross_{i,i}$ not $cross_{i,j}$

  • 0
    @Bria$n$M.Scott, you are right i should find better bramble, i'd edited my answer respect to your comment.2012-01-14