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

Question

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.

Answer 1

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.