Many thanks for your suggestions! I am Sam's coauthor, but first need to gain some reputation to comment directly on your replies.
In our previous attempts at solving the problem, we came accross a particular graph, which indicates that a path/cycle-based condition (such as one-sided versions of the periodic point condition suggested by Ville Salo) is not sufficient. The graph $G = (V,R_0,R_1)$ (we call it the "Hamburger") is as follows:
- $V = \{a,b,c\}$,
- $R_0 = \{(a,a), (a,c), (c,a), (c,b), (b,c), (b,a)\} = (V \times V) \setminus \{(a,b), (c,c), (b,b)\}$, and
- $R_1 = \{(b,b), (b,c), (c,b), (c,a), (a,c), (a,b)\} = (V \times V) \setminus \{(b,a), (c,c), (a,a)\}$.
In this graph all sorts of cycles exist and for sufficiently long words there are paths between any two vertices: Writing $R_w = R_{w_1} \circ \dots \circ R_{w_n}$ for a word $w = w_1 \dots w_n$, we get that:
- $R_{00} = R_{10} = (V \times V) \setminus \{(c,b)\}$,
- $R_{11} = R_{01} = (V \times V) \setminus \{(c,a)\}$, and
- $R_w = V \times V$ for every $w$ with $|w| \geq 3$.
One can show that there is no surjective homomorphism $B_n \to G$ for any $n$. One strategy is to observe that there is no subgraph of the kind mentioned by 1001 in their reply. Starting from the singletons $\{a\}$, $\{c\}$ and $\{b\}$ one can reach $\{a,b\}$ from $\{c\}$ via both a $0$ and a $1$-edge. But then one is stuck and no additional subsets can be connected to the singleton part.
