5
$\begingroup$

Let $G$ be a connected graph with vertices $V(G)$. A bramble of $G$ is a set of connected subgraphs $H_1,\ldots,H_n$ such that for each $i$ and $j$, $H_i$ touches $H_j$; that is, either $H_i$ intersects $H_j$ in a vertex, or there is an edge in $G$ that connects a vertex of $H_i$ to a vertex of $H_j$. The order of a bramble is the minimum size of a set $S\subset V(G)$ such that $S\cap H_i$ is nonempty for all $i$. Then, the bramble number of $G$, denoted $Br(G)$, is the largest order of any bramble of $G$.

A strict bramble of $G$ is a set of connected subgraphs $H_1,\ldots,H_n$ such that for each $i$ and $j$, $H_i$ intersects $H_j$ in a vertex. The order of a strict bramble is similarly the minimum size of a set $S\subset V(G)$ such that $S\cap H_i$ is nonempty for all $i$, and the strict bramble number of $G$, denoted $sBr(G)$, is the largest order of any strict bramble of $G$. (Strict brambles are sometimes called intersecting families, and the strict bramble number is sometimes called the “PI number" for “pairwise intersecting”.)

Since any strict bramble is also a bramble, we have $sBr(G)\leq Br(G)$ for all graphs $G$. My question is this: do we ever have $sBr(G)=Br(G)$? Or is it always the case that if there exists a strict bramble of order $k$, there exists a bramble of order $k+1$?

Edit: they are equal if G consists of one vertex and no edges. Are there any graphs with two or more vertices for which they are equal? (Thanks to Arun for pointing this out!)

(See this post for more discussion on bramble number and strict bramble number.)

$\endgroup$
4
  • 1
    $\begingroup$ If I understand everything correctly, when $G$ has a single vertex and no edges, both $\mathit{Br}(G)$ and $\mathit{sBr}(G)$ are equal to 1. $\endgroup$ Jul 31, 2018 at 15:50
  • $\begingroup$ You’re absolutely right! I edited the question to ask if there are any other graphs. $\endgroup$ Jul 31, 2018 at 16:38
  • 1
    $\begingroup$ For $k\ge 2$, the $k\times k$ square grid has bramble number $k+1$ and strict bramble number at least $k$. $\endgroup$
    – Jan Kyncl
    Jul 31, 2018 at 21:55
  • $\begingroup$ I agree; in fact, the strict bramble number for the square grid is exactly $k$, by results in the this thesis by Josse van Dobben de Bruyn: universiteitleiden.nl/binaries/content/assets/science/mi/… Indeed, the two numbers differ by exactly 1 for any rectangular grid. My hope is that this gap is always at least 1, for graphs that have at least 2 vertices. $\endgroup$ Aug 1, 2018 at 2:20

1 Answer 1

3
$\begingroup$

Indeed, for every connected graph $G$ with at least two vertices, we have $sBr(G)<Br(G)$. This follows from a theorem by Seymour and Thomas and its proof (Theorem 12.4.3 in Reinhard Diestel, Graph Theory, Springer GTM 173, 5th edition 2016). The theorem states that the treewidth of $G$ is equal to $Br(G)-1$.

Let $k=\mathrm{Br}(G)-1=\mathrm{tw}(G)$. By the assumption, $G$ has an edge, so it has a bramble of order $2$ and so $k\ge 1$. Let $(T,\mathcal{V})$ be a tree decomposition of $G$ of width $k$. This implies that for every edge $t_1t_2$ of the tree $T$, the intersection $V_{t_1}\cap V_{t_2}$ has at most $k$ vertices, since we can assume that the sets $V_t \in \mathcal{V}$ are pairwise distinct.

Let $\mathcal{B}$ be a strict bramble in $G$. By the proof of Theorem 12.4.3, at least one of the following possibilities happens:

1) there is an edge $t_1t_2$ of $T$ such that $V_{t_1}\cap V_{t_2}$ covers $\mathcal{B}$: in this case the order of $\mathcal{B}$ is at most $k$.

2) there is a node $t$ of $T$ such that $V_t$ covers $\mathcal{B}$, and we can assume that case 1) does not occur. We may assume that $|V_t|=k+1$ and we want to show that a proper subset of $V_t$ of $k$ vertices is sufficient to cover $\mathcal{B}$.

If $G$ has only $k+1$ vertices, then either $\mathcal{B}$ contains a singleton set, in which case $\mathcal{B}$ has order $1$, otherwise an arbitrary vertex of $V_t$ can be omitted and the remaining $k$ still cover $\mathcal{B}$.

If $G$ has at least $k+2$ vertices, then $T$ has an edge $tt'$ such that $|V_t\cap V_{t'}|\ge 1$. By Lemma 12.3.1 in Diestel's book, $V_t\cap V_{t'}$ separates the sets of vertices of $G$ induced by the two components of $T-tt'$.

I claim that $V_t\setminus V_{t'}$ covers $\mathcal{B}$. If not, there would be a set $B' \in \mathcal{B}$ disjoint with $V_t\setminus V_{t'}$, but also a set $B \in \mathcal{B}$ disjoint with $V_t\cap V_{t'}$ (by the assumption that $V_t\cap V_{t'}$ does not cover $\mathcal{B}$). By the previous paragraph, this means that $B$ and $B'$ are disjoint, which contradicts the strictness of $\mathcal{B}$.

$\endgroup$
0

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.