7
$\begingroup$

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, w\}\in E(G)$ implies $\{f(v), f(w)\} \in E(H)$.

We say that a graph homomorphism $u:G\to H$ is universal if for every graph homomorphism $f:G\to H$ there is $v \in V$ such that $f(v) = u(v)$.

Is the composition of two universal graph homomorphisms universal?

$\endgroup$
7
$\begingroup$

Ok, try again.

Let $G_k=W_{2k+5}\cup W_{2k+1}$, where $W_k$ is the wheel with $k$ spokes. Then for $k\ge 3$, every homomorphism $G_k\to G_{k-1}$ fixes the hub of the smaller wheel as there is no homomorphism $W_{2k+1}\to W_{2k+3}$, and every homomorphism $W_{2k+1}\to W_{2k-1}$ fixes the hub.

Now let $\phi_k:G_k\to G_{k-1}$ be injective homomorphisms (so the bigger wheel goes to the bigger wheel, the smaller to the smaller). Each of these is universal by the argument above. But if you you combine $\phi_{k+1}$ and $\phi_{k}$, the resulting homomorphism $G_{k+1}\to G_{k-1}$ is not universal: just use a homomorphism that switches the wheels.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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