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.



What is the relationship between the bramble number and the strict bramble number of a graph?
**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.


