Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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). –  Ali Amiri 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 :) –  Ali Amiri Jan 14 '12 at 19:42
    
+1 for correct answer –  Ali Amiri 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}$

share|improve this answer
    
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
1  
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. –  Ali Amiri Jan 14 '12 at 18:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.