Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?

Question

Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ is finite.

When $G$ is no longer finite, this no longer holds: consider the graph whose vertices are the integers, with an edge between every neighboring pair of positive integers, and the endomorphism $f(n)=1+n$. The vertices are in bijection, all pairs of neighboring positive integers get mapped to new pairs of neighboring positive integers, so it's a homeomorphism. But the previously non-adjacent $(0,1) \to (f(0),f(1)) = (1,2)$ which is adjacent. So $f$ is not an isomorphism.

However, $f$ restricts to an isomorphism on most of its domain: restricting it to $H=\mathbb{Z}\setminus\{0\}$ or $\mathbb{Z}\setminus\{1\}$ produces an isomorphism. (Not an automorphism of subgraphs, because the domain and range are not the same.) This is a "large" restriction in the sense that $|G|=|H|$.

Given how nicely this works for finite graphs and all the infinite examples I could think of... can we always find such a restriction?

Answer 1

The answer is yes for countable graphs:

Fix an infinite graph $G$ and a bijective homomorphism $f:G \to G$. Define $c:[G]^2 \to 2$ as $c(\alpha,\beta)=1$ if $\{f\alpha, f\beta\} \in E(G)$ and $c(\alpha,\beta)=0$ otherwise. Since $G$ is infinite, by Ramsey´s Theorem there is an infinite $c$-homogeneous $H \subseteq G$. If $c \upharpoonright [H]^2$ is constant $0$ then $f \upharpoonright H$ is an isomorphism. If $c \upharpoonright [H]^2$ is constant $1$ then $f \upharpoonright f(H)$ is an isomorphism.

The answer is no for graphs of size $\aleph_1$:

Fix a coloring $c:[\omega_1]^2 \to \mathbb{Z}$ with the property that for all uncountable $A\subseteq \omega_1$ and for all $n \in \mathbb{Z}$ there are $\alpha,\beta \in A$ such that $c(\alpha,\beta)=n$. Such a coloring was constructed by S. Todorcevic in the 1980's, using his method of minimal walks.

Define a graph $G$ by $V(G)=\omega_1 \times \mathbb{Z}$ and $E(G)=\{\{(\alpha,n),(\beta,n)\} : c(\alpha,\beta) < n\}$. Consider the function $f:G \to G$ defined by $f(\alpha,n)=(\alpha,n+1)$. It should be clear that $f$ is a bijective homomorphism. However, if $H \subseteq G$ is uncountable, then there is an $n_0 \in \mathbb{Z}$ such that the set $A=\{\alpha: (\alpha,n_0) \in H\}$ is uncountable. So we can find $\alpha, \beta \in A$ such that $c(\alpha,\beta)=n_0$ and thus the pair $\{(\alpha,n_0),(\beta,n_0)\}$ witnesses the fact that $f \upharpoonright H$ is not an isomorphism.

For other cardinals:

Todorcevic´s function and the corresponding graph can be constructed for any successor cardinal so for those the answer is no. For weakly compact cardinals we can repeat the countable case argument so the answer is yes for those. I guess this still leaves infinitely many open questions.