# Infinite strongly rigid graphs

Is there an infinite connected simple undirected graph $G=(V, E)$ such that the identity map $\text{id}_V: V\to V$ is the only graph self-homomorphism from $G$ to itself?

(A graph self-homomorphism is a map $f: V\to V$ such that for all $e\in E$ with $e = \{v, w\}$ we have $\{f(v), f(w)\} \in E$.)

• I would expect the answer is yes (without having checked all the details) because you should be able to code up some other strongly rigid structure, like the total order $(\omega,<)$, into a connected simple graph, a la Joel's answer here: mathoverflow.net/questions/281039/… – Will Brian Nov 17 '17 at 13:50
• Thanks for that idea, I get the feeling this could be made to work... – Dominic van der Zypen Nov 17 '17 at 14:33

Unfortunately, I don't have enough reputation to comment, but there seems to be a problem with both solutions suggested so far: The graphs are bipartite, meaning that they allow a homomorphism to a single edge, which of course is a non-trivial homomorphism from the graph to itself (note that homomorphisms are not assumed to be injective).

However, here is a more complicated construction which hopefully takes care of this:

Let $H_0 = K_3$. For $i \geq 1$ let $H_i$ be a triangle free graph such that $\chi(H_i) > \chi(H_{i-1})$ and such that the only homomorphisms from $H_i$ to itself are automorphisms (there is for example a family of Kneser graphs with this property).

Enumerate the vertices of the disjoint union $\bigcup _{i \geq 0} H_i$ as $(v_j)_{j \geq 1}$ such that $v_j \in H_i$ for some $i < j$.

Now define a sequence $G_n$ as follows:

• $G_0 = H_0$.
• For $i > 0$ let $l$ be the maximum of the diameters of $G_{i-1}$ and $H_i$ and connect one vertex of $H_i$ to $v_i$ by a path of length $l$.
• Let $G$ be the direct limit of this construction.

There is no homomorphism from $K_3$ to a triangle free graph, hence $G_0$ must be fixed by every homomorphism.

There is no homomorphism from $G$ to $H$ if $\chi (H) < \chi (G)$, hence $H_i$ cannot be mapped into $G_{i-1}$ (plus the paths leading to $H_j$ for $j>i$). Since Homomorphisms never increase distances, i.e. if $f$ is a homomorphism, then $d(x,y) \geq d(f(x),f(y))$, this together with the fact that $d(H_i,H_0)$ is bounded by the diameter of $G_i$ implies that the image of $H_i$ must intersect $H_i$. Consequently $H_i$ must map to itself---if the image of $H_i$ intersected one of the paths attached to $H_i$, then this would give a homomorphism $H_i \to H_i$ which is not an automorphism.

So far we showed that each $H_i$ is fixed setwise by every self-homomorphism of $G$. Finally, the structure between the $H_i$ guarantees that every $H_i$ must be fixed pointwise: if $v_j \in H_i$, then it is the unique vertex in $H_i$ which minimises the distance to $H_j$.

• Thanks Florian - have to think again about the solutions! – Dominic van der Zypen Nov 18 '17 at 16:56

Start with the integer line $\mathbb Z$, and take a subset $A\subset\mathbb Z$ which is not fixed by any automorhism of the graph $\mathbb Z$. Then the tree obtained from $\mathbb Z$ by attaching a leaf to any vertex from $A$ is rigid.

This is essentially a variation of the construction of rigid graphs by vertex coloring (for instance, see Random colorings and automorphism breaking in locally finite graphs by Florian Lehner).

Here is a simple construction. Start with a long finite path of length $\ell_1$ and put the vertices of degrees $3$ and $4$ at the ends. Now we want to ensure that there are no other pairs of vertices of degree $>2$ at distance $\ell_1$. This will force the homomorphism to be trivial on the path we have. So, just start drawing some longer paths from the branching points and place the vertex of degree $3$ at one of them at some distance $\ell_2\gg \ell_1$. This will fix that path if we ensure that now there is no other vertex of degree $>2$ at distance $\le\ell_2$ from the (already pinned) 2 vertices of high degree. Now we have $3$ pinned vertices and paths going out of them, etc. If you do the stopping and branching in some reasonable order, you'll get an infinite graph in which all is pinned. Of course, it is the same ordinal business but without high-tech.