5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow! What an amazingly unexpected answer! I absolutely did not expect it to depend so sensitively on the cardinality. To check that I understand: if Q is the successor cardinal of P, the Todorcevic construction uses $V(G)=Q\times P$? It's known that such a $P$-coloring of $K_Q$ will always exist? The mapping $f$ requires ordering $P$ as $P$ successive copies of $\mathbb{Z}$? Thank you! $\endgroup$ – Alex Meiburg Feb 10 at 19:52
  • 1
    $\begingroup$ @AlexMeiburg, Sorry if I was too vague. Todorcevic showed that for any successor cardinal $\kappa$ there exists a coloring $c:[\kappa]^2 \to \omega$ such that for any $A \subseteq \kappa$ of size $\kappa$, the restriction of $c$ to $A$ takes all possible colors. The structure of the set of colors is irrelevant so we can always make it $\mathbb{Z}$ which allows us to construct $G$ and $f$ just as we did with $\omega_1$. $\endgroup$ – Ramiro de la Vega Feb 10 at 20:17
  • $\begingroup$ Mm, right, makes sense now. Thank you! $\endgroup$ – Alex Meiburg Feb 10 at 20:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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