# What is the relationship between the bramble number and the strict bramble number of a graph?

A bramble in a graph $G$ is a set of connected subgraphs $H_1, \dots, H_m$ such that for every $i, j$, either $H_i$ intersects $H_j$ in a vertex, or there exists an edge of $G$ with one end in $V(H_i)$ and one end in $V(H_j)$. The order of the bramble is the minimum $|X|$ such that $X \subseteq V(G)$ and $X \cap V(H_i) \neq \emptyset$ for all $i$. The bramble number of $G$ is the maximum order of a bramble in $G$. Denote it $Br(G)$.

Say a strict bramble in a graph $G$ is a set of connected subgraphs $H_1, \dots, H_m$ such that for all $i, j$, $H_i$ intersects $H_j$ in a vertex. Definite analogously the order of a strict bramble and the strict bramble number of a graph, and denote the strict bramble number by $sBr(G)$.

Clearly, the bramble number is at least the strict bramble number. They also won't be equal in general. For example, in $K_t$, the bramble number is $t$, but the strict bramble number will be essentially $t/2$.

Is this tight? Is it true that $sBr(G) \ge Br(G)/2$? The grid theorem implies that there is a function $f$ such that the $sBr(G) \ge f(Br(G))$, but it might be true as well with a linear function.

• Just a note -- your definition of the order of a bramble is a bit unclear, I had to go look it up elsewhere. It's the smallest size of a set of vertices, such that that set intersects each $H_i$. Sep 13, 2013 at 21:04
• Thanks - I restated the definition and it should be more clear now. Sep 13, 2013 at 22:51

Yes, $sBr(G) \geq Br(G)/2$ for all graphs $G$.
To see this, let $\mathcal{Y}:=Y_1, \dots, Y_m$ be a bramble of $G$ with a minimum hitting set $X$ such that $|X|=br(G)$. It will be slightly more convenient to let $Y_i$ be sets of vertices which induce connected subgraphs. For each $x \in X$, let $\mathcal{Y}_x$ be the sets of $Y_1, \dots, Y_m$ that $x$ belongs to. For each subset of $X'$ of $X$, let $\mathcal{F}(X')$ be the family of sets of the form $\bigcup_{x \in X'} Y_x$, where $Y_x \in \mathcal{Y}_x$. Finally, let $\mathcal{B}$ be the family of sets obtained by taking the union of $\mathcal{F}(X')$ over all subsets $X'$ of $X$ of size $k:=\lfloor Br(G)/2\rfloor+1$.
Note that since $\mathcal{Y}$ is a bramble, each set in $\mathcal{B}$ does induce a connected subgraph. Moreover, $\mathcal{B}$ is a strict bramble since any two sets in $\mathcal{B}$ meet in a vertex of $X$. Finally, I claim that every hitting set of $\mathcal{B}$ has size at least $Br(G)/2$. If not, then there is a hitting set $Z$ for $\mathcal{B}$ of size $k'<Br(G)/2$. Let $\mathcal{Y}'$ be the sets of $\mathcal{Y}$ that $Z$ does not meet. Define $X'$ to be set of vertices $x \in X$ such that $x \in \bigcup \mathcal{Y}'$. By definition of $\mathcal{B}$, we have that $|X'| \leq k-1$. Since $X$ is a hitting set of $\mathcal{Y}$, we have that $X'$ is a hitting set for $\mathcal{Y}'$. Thus $Z \cup X'$ is a hitting set for $\mathcal{Y}$ of size at most $k' + (k-1) < |X|$, which is a contradiction.
• I think this actually proves it's at least $\lceil Br(G)/2 \rceil$ -- if $Br(G)$ is even we are done, and if $Br(G)$ is odd note that the argument yields a contradiction even if $k'=k-1$. Sep 14, 2013 at 19:19
• Hi Tony, thanks! One quick comment on the proof. I think after defining $\mathcal{Y}'$, you want to define $\bar{X} \subseteq X$ to be the set of $x \in X$ such that there exists a $Y \in \mathcal{Y}'$ with $x \in Y$. Then given that $Z$ is a hitting set for $\mathcal{Y}$ and the definition of $\mathcal{B}$, we have that $|\bar{X}| \le k-1$. (But I don't think we get a bound on $|\mathcal{Y}'|$). Then $Z \cup \bar{X}$ is hitting set yielding a contradiction. Sep 15, 2013 at 22:15