# k×k grid has tree-width at least k

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.

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?

-
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$. – Brian M. Scott Jan 14 '12 at 17:29

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.

-
No we both have same mistake, crosses doesn't cause to bramble of order k in k*k grid, you just need to select intersection of two cross to make a hitting set which causes to Floor(k/2) not k, i thought about it and I see it's wrong (Still I didn't edit my answer because I couldn't find any way). – Lrrr Jan 14 '12 at 19:30
@Ali: If you use all $k^2$ crosses ($\operatorname{row}_i\cup\operatorname{col}_j$ for $1\le i,j\le k$, you do get a bramble of order $k$: any set of fewer than $k$ points misses at least one row and column and therefore misses at least one cross. – Brian M. Scott Jan 14 '12 at 19:36
You take all the crosses right :) it was simple mistake i made :) – Lrrr Jan 14 '12 at 19:42
+1 for correct answer – Lrrr Jan 14 '12 at 19:47
@BrianM.Scott: Thank you very much for the answer, I very appreciate it. My problem is I cannot get the idea behind the bramble, it's not actually a cover, it contains joined and disjoined connected by edge subgraphs. What the intuition of the bramble? I don't get the proof from Diestel's book too, because of the same reason - bramble. And how they get the path on the 5th slide, there is also should be something behind it. – com Jan 15 '12 at 20:33

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}$

-
Your bramble of order $n$ shows only that the treewidth of the $n\times n$ grid is at least $n-1$. – Brian M. Scott Jan 14 '12 at 17:34
That’s irrelevant to the point that I was making. You said that the bramble of crosses shows that the treewidth is at least $n$, but it doesn’t: it shows only that the treewidth is at least $n-1$. Thus, finding a tree decomposition of width $n$ leaves open the possibility that the treewidth is actually $n-1$. Your argument would be incomplete even if you had included the tree decomposition of width $n$. – Brian M. Scott Jan 14 '12 at 18:03
@BrianM.Scott, you are right i should find better bramble, i'd edited my answer respect to your comment. – Lrrr Jan 14 '12 at 18:29