10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Sep 13, 2013 at 21:04
  • $\begingroup$ Thanks - I restated the definition and it should be more clear now. $\endgroup$ Sep 13, 2013 at 22:51

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 14, 2013 at 19:19
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 15, 2013 at 22:15
  • $\begingroup$ @HarryAltman, Yes, you are right the proof does indeed show more. I edited accordingly. $\endgroup$
    – Tony Huynh
    Sep 15, 2013 at 22:24
  • $\begingroup$ @PaulWollan, You're welcome! And yes you are right, I edited the proof accordingly. $\endgroup$
    – Tony Huynh
    Sep 15, 2013 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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