Let $G=(V,E)$ be an countably infinite, locally finite transitive graph. Say that $G$ is exchangeable if for every two vertices $v,w \in V$ there exists a graph homomorphism that maps $v$ to $w$ and $w$ to $v$. Certainly such a graph has a unimodular automorphism group. Is there an example of a graph $G$ that is not exchangeable but is unimodular?

  • 1
    $\begingroup$ how is exchangeable different than vertex transitive? $\endgroup$ – Benjamin Steinberg Feb 10 '14 at 20:40
  • $\begingroup$ You are absolutely right - I left out the main point. Now edited to make sense. $\endgroup$ – Vladimir Feb 11 '14 at 1:32
  • $\begingroup$ There was a mistake in the initial phrasing of the problem. This mistake is now fixed. $\endgroup$ – Vladimir Feb 12 '14 at 14:06

The standard Cayley graph $\Gamma$ of the Baumslag-Solitar group $BS(1,2) = \langle a,b \mid bab^{-1} = a^2 \rangle$ is non-exchangable and unimodular (as is any Cayley graph). See http://en.wikipedia.org/wiki/Baumslag-Solitar_group for a picture of $\Gamma$. To see non-exchangability, observe the following:

  1. an edge is labeled by $a$ iff it is contained in three distinct $5$-cycles, and by $b$ iff it is contained in two distinct $5$-cycles. Hence $\mathrm{Aut}(\Gamma)$ preserves the labeling of the (unoriented) edges by $a$ or $b$.
  2. any $5$-cycles contains two $a$-labeled components, one with two edges and one with a single edge. Given any $5$-cycle, an oriented edge in the cycle is of the form $(g, gb)$ iff it points towards the $a$-labeled component with a single edge. It follows that $\mathrm{Aut}(\Gamma)$ preserves the oriented labeling of the $b$-labeled edges.

Consequently, there is no automorphism of $\Gamma$ which exchanges the vertices $1$ and $b$.


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.