# Does the “free category on a reflexive graph” monad preserve weak pullbacks, and “why”?

Consider the category of reflexive graphs, and the monad $M$ on it taking the free category: $M(G)$ has all vertices of $G$ as objects, and as edges $x \to x'$ all identity-free paths $x \to x'$ in $G$.

This monad does not preserve pullbacks (it preserves the terminal object but not the product of $2$ with itself, where $2$ is the two-element poset $0 \leq 1$ viewed as a reflexive graph).

Does $M$ preserve weak pullbacks?

If so, since $M$ does not admit weak factorisations (in the sense of Mark Weber's "Generic morphisms, parametric representations, and weakly cartesian monads", TAC 13(14), 2004), is there a good explanation of what's going on?

-
Dear @Tom Hirschowitz, can you please clarify what the expression "what's going on" in the last question is referring to? – Ricardo Andrade Mar 28 '14 at 17:08
Can try. Mark shows that weak generic factorisations imply preservation of weak pullbacks, and André Joyal has shown that in the case of endofunctors on sets, up to mild conditions, the converse also holds. So the question is: has anyone figured out general conditions for the converse implication to hold? – Tom Hirschowitz Mar 28 '14 at 17:19
I think i have a proof that $M$ does indeed preserve weak pullbacks. I'll try to write it down asap. – Tom Hirschowitz Mar 28 '14 at 21:03
What are weak pullbacks of reflexive graphs? – Omar Antolín-Camarena May 29 '14 at 19:10
@OmarAntolín-Camarena, in any category a weak pullback is a square that satisfies the universal property of a pullback, but without the uniqueness requirement. A weak pullback of reflexive graphs is a weak pullback in the category of reflexive graphs. – Tom Hirschowitz Jun 5 '14 at 11:49

Here's a tentative answer to the first question. I'd be glad for any comment, and hints regarding the second question!

Let $B \xleftarrow{p} A \xrightarrow{q} C$ be a weak pullback of $B \xrightarrow{f} D \xleftarrow{g} C$, and consider any span $B \xleftarrow{u} G \xrightarrow{v} C$ such that $fu = gv$.

Consider the pullback $B \xleftarrow{\pi} P \xrightarrow{\pi'} C$ of $f$ and $g$, which is constructed just as in graphs, with identities given by pairs of identities.

For any edge $e \colon x \to x'$ in $G$, we construct an identity-free path $p_e \colon (u(x),v(x)) \to^\star (u(y),v(y))$ in $P$, by induction on the lengths of $u(e)$ and $v(e)$ (which are identity-free paths in $B$ and $C$, respectively):

• if one is the empty path, w.l.o.g. $u(e)$ is the empty path on, say, $B_0$, then the other, say $C_0 \xrightarrow{c_1} C_1 \ldots \xrightarrow{c_n} C_n$, must map to an identity-only path in $D$, and we let $e_p$ consist of all pairs $(id_{B_0}, c_i)$, which do form a path in $P$;

• otherwise, we consider the first edges $b_1$ and $c_1$:

• if none of them maps to an identity (by $f$ resp. $g$), then we pick $(b_1,c_1)$ as the first edge of $e_p$ and continue by induction;

• if at least one of them, w.l.o.g. $b_1$, maps to an identity, then we pick $(b_1, id)$ and continue by induction (note that in this case we do not decrease the length of the image path in $D$).

Let $l_e$ be the length of $p_e$.

Now, let $G'$ denote the free reflexive graph with

• as vertices those of $G$, plus $l_e - 1$ vertices $x^e_1, \ldots, x^e_{l_e - 1}$ for each edge $e$ of $G$,

• for each edge $e \colon x \to x'$ of $G$, a path $x \to x^e_1 \to \ldots \to x^e_{l_e - 1} \to x'$ (i.e., really $l_e$ edges).

Our paths $e_p$ determine a morphism $k \colon G' \to P$ of reflexive graphs, such that $\pi k$ and $\pi' k$ coincide with $u$ and $v$ on vertices, and $f \pi k = g \pi' k$.

Thus by universal property of weak pullback, we obtain a morphism $h \colon G' \to A$ such that $p h = \pi k$ and $q h = \pi' k$.

This yields a morphism $M(h) \colon M(G') \to M(A)$ such that $M(p) M(h)$ and $M(q) M(h)$ respectively map each $p_e$, viewed as an edge in $M(G')$, to $u(e)$ and $v(e)$. Precomposing with the morphism $G \to M(G')$ mapping each $e$ to $p_e$, we obtain the desired morphism $j \colon G \to M(A)$ such that $M(p) (j(e)) = u(e)$ and $M(q) (j(e)) = v(e)$.

-