Show Automorphism Group Generated by s and t for \mathbb{Z} Graph

[Oxymoron]

I have a combinatorial graph with vertex set $\mathbb{Z}$ such that the set $\{\{i,i+1\}\,:\,i\in\mathbb{Z}\}$, which are the geometric edges, is its geometric realization. The graph is basically the real line with vertices on the integers, and where every edge connects an integer i with i-1 and i+1.

As well as having this graph, I have been given two automorphisms

$$s(i):=-i$$

$$t(i):=-i+1$$

defined on the vertices of the graph. My task is to show that these two automotphisms generate the automorphism group of the graph.


Questions:
[1] It is my understanding that an automorphism group contains automorphisms as "elements" (I'm used to thinking of groups as collections of objects that satisfy the four group axioms). Is this right?

[2] To show that my two automorphisms generate an automorphism group of this graph must I show the following four things:

i) Closure: The composition of the given 2 automorphisms in any way returns a composition of automorphisms.
ii) Associativity: $$(s\circ t) \circ s = s\circ (t\circ s)$$ and $$(s\circ t)\circ t = s\circ (t \circ t)$$.
iii) Identity: This is easy, right? Is the identity automorphism simply $s\circ s$? Or $t\circ t$? Both composition automorphisms map i to i. Perhaps I am getting this confused with s(0) = 0? I don't know!
iv) Inverse: Surely s(i) is the inverse automorphism. Since s(i) maps i to -i.

If I show all four of these then have I shown that s and t generate the automorphism group for the graph?

 

[AKG]

[1] It is my understanding that an automorphism group contains automorphisms as "elements" (I'm used to thinking of groups as collections of objects that satisfy the four group axioms). Is this right?

Yes. In this case, your objects are automorphisms.

Now, are you to take for granted that the collection of automorphisms of this graph form a group under composition? If so, skip this paragraph. If not, then you need to show that composition is indeed a closed operation on automorphism, that composition is associative, that there is an identity element, and that every automorphism of the graph has an inverse which is also an automorphism of the grass. This should all be done with no regard to s or t.

To check that s and t generate the group, show that an arbitrary automorphism of the graph can be expressed as some product of s, t, s^-1, and t^-1.

 

[Oxymoron]

Posted by AKG

...This should all be done with no regard to s or t.

You're right. To show that composition of automorphisms is closed I mustn't use only s and t but rather any arbitrary automorphisms a,b. I suppose that isn't exactly what I need to know (as in, I think I can take that for granted) but, of course, I will endeavor to show it in any case.

Posted by AKG

To check that s and t generate the group, show that an arbitrary automorphism of the graph can be expressed as some product of s, t, s-1, and t-1.

An automorphism is a mapping which takes a vertex in the graph and produces another vertex in the graph which is connected by an edge (where the edges are defined in post #1). Does this sound right? I mean, it makes sense to understand what an arbitrary automorphism of this graph is before I begin to solve the problem.

EDIT 1: Is the following a definition of an automorphism for my case?

An automorphism a(i) is a mapping defined on the vertices of the graph such that it preserves edges.

That is, if two vertices, $i,j$ are connected by an edge $e_{i,j}$ then $a(i),a(j)$ will be connected by an edge $e_{a(i),a(j)}$. Is the correct?

EDIT 2: So for example, $a(i):=3i$ is not an automorphism because 1 maps to 3 and 2 maps to 6, but 3 and 6 are not connected by an edge whereas 1 and 2 are.

I ask this because when considering arbitrary automorphisms (to see if they can be specified as a composition of s and t) I must take note because not every linear function I can dream up (such as the a(i) given here) is not necessarily an automorphism on the vertices of my graph. Unless, of course, I am completely wrong.

 

[Oxymoron]

So basically I have to prove that given any automorphism $a(i)$ defined on the vertices of my graph, it can be specified as a composition of $s,t,s^{-1},t^{-1}$. But what are $s^{-1},t^{-1}$? They are the inverse automorphisms are they not? But s maps i to -i which means that $s^{-1}$ maps i to -i, and $t^{-1}$ maps i to -i+1, so essentially $s(i) = s^{-1}(i)$ and $t(i) = t^{-1}(i)$.

If this reasoning is correct, then I only have 2 automorphisms with which to specifiy an aribtrary automorphism.

 

[Oxymoron]

ASIDE: This is starting to look like a very easy question. I understand that the automorphism group $\mbox{Aut}G$ is the set of all permutations of a graph that constitute a group under composition - where each permutation (or automorphism) of the vertices of the graph preserve the edge. I can image there would be plenty of permutations (or automorphisms) of graphs (such as the Dihedral) which preserve edges. But in my case, where the graph is the real line with vertices on the integers, there are only two types of permutations (automorphisms) which preserve the edge:

$$a_1(i):=i+n$$
$$a_2(i):=-i+n$$

where $$n \in \mathbb{Z}$$.

I cannot think of any other permutations on the i's such that if i,j are two vertices connected by an edge, then a(i),a(j) is also connected by an edge.

So this limits the possible automorphisms on the graph. For example, it does not include automorphisms of the following sort:

$$a_3(i):=\lambda_1 i + \lambda_2\quad\lambda_1,\lambda_2 \in \mathbb{Z}$$

 

[AKG]

Post #4 is correct. So, if your homework problem demands it, show that the collection of automorphism do indeed form a group under composition. Then show that any arbitrary isomorphism can be expressed as some combination of s and t, i.e. show that s and t generate the group.

 

[matt grime]

Ok, this is really, very obvious, and I can't believe it has taken more than one post to clear this up.

Whenever you have to construct th automorphisms of some object just think what the autos can do. If f sends i to j what extra information is required to fix f? Exactly one more: where i+1 (or i-1) goes. From this it is clear that your two autos generate the group.

one is the inversion operation, and the the composition of the two is the shift operator.

 

[Oxymoron]

Posted by Matt Grime:

...what extra information is required to fix f?

Sorry Matt, I am not sure what you mean by this. Why are we "fixing" the automorphism? Is f supposed to be my "arbitrary automorphism" which I am trying to specify with s and t to show it generates AutG?

Posted by Matt Grime:

From this it is clear that your two autos generate the group.

So you are saying that it is clear that s and t generate AutG once I know what happens to every vertex (and every neighbour of that vertex - i.e. i+1 and i-1) under s and t? If this is correct I don't understand why this is all I need to know. Because...

$$s(i):i\mapsto -i$$
$$s(i+1):i+1\mapsto -i-1$$
$$s(i-1):i-1\mapsto -i+1$$

$$t(i):i\mapsto -i+1$$
$$t(i+1):i+1\mapsto -i$$
$$t(i-1):i-1\mapsto -i+2$$

This shows where each vertex i and it's neighbours i+1 and i-1 get mapped too. Should I be noticing something here?

 

[Oxymoron]

I do notice that

$$(t\circ s)(i):=i+1$$

which I guess is the "shift" automorphism Matt was talking about. And then

$$(s\circ t)(i):=i-1$$

which shifts vertices backward one vertex (all the while preserving edges because the composition is of the form i found earlier: $\pm i +n$, with $n\in\mathbb{Z}$.

But with this composition (which I know is closed in AutG) I can move from any vertex to another (preserving edges as I go). So since an automorphism is a map from the graph to itself on vertices, then no matter where an arbitrary automorphism maps a vertex to, I can always represent this mapping as a number of [itex](t\circ s)[/tex]'s and $(s\circ t)$'s.

Does this sound right?

EDIT: So for example, the following automorphism (yes, I believe it is an automorphism)

$$\phi(i):=i+3$$

can be written as

$$\phi(i) = (t\circ s)^3(i)$$

and

$$\phi(i):=i-3=(s\circ t)^3(i)$$

PS: What is a presentation of a group?

 

[matt grime]

A presentation of a group is a set of elements, which we'll call Gens, and a set of relations, Rels. An element of Rel is a word or an eqaution in words in the elements of gen and their inverses, usually it is understood that a relation like g^2 means g^2=e.

The dihedral group has presentation D_n=< s,t | s^2=t^n=e and sts=t^-1>.

Presentations are not unique, and it is often hard to tell when two groups are isomorphic given two presentations. For instance D_3 is isomorphic to S_3 and a presentation of S_3 could be <i,j,k| i^2=j^2=k^2=e, ij=ki> which I think is enough to specify it (it is the 2-cycles in S_3 I'm trying to use as generators)

 

[Oxymoron]

How do you tell that the Gens and Rels constitute a presentation? I mean, how do you know that

$$D_n = \langle s,t\,|\,s^2=t^n=e \wedge sts=t^{-1}\rangle$$

is a presentation for the Dihedral group?

Would

$$\langle s,t\,|\,s^2=t^2=1\rangle$$

be a presentation for my automorphism group that we have been discussing? Since I figured that s and t are generators (which you guys have been telling me) and $s^2=t^2=1$ is a "word" or "equation in words" of generators and their inverses as Matt said. Should this be enough to convince me that this is a presentation of my automorphism group, or should I prove more?

 

[matt grime]

That isn't a presentation. Or at least it is not a presentation of the group you are using. You need to specify *all* relations, or something that implies all true relations. And if you omit any relations then they are assumed false.

What you have written down is a presentation of C_2*C_2 (that is the free product, not the direct product).

Presentations aren't things that are discussed much these days, it seems. I was certainly never taught about them.

So, if you just specify s^2=t^2=e, then we cannot use the relations to simplify sts, say, thus the group is the set of all words in s and t (and their inverses) with the *only* relation that s^2=t^2=e, and that certainly is not your group (at least It does not obviously seem to be your group). Your group is the semi direct product of Z with C_2.

 

[AKG]

Gens and Rels always constitute a presentation. How you know a given presentation is the presentation of a particular group, like the Dihedral group, is a different question. The way I'm used to seeing it, all the words in Rels are written so that they equal e, so instead of:

$$s^2 = t^n = e\wedge sts = t^{-1}$$

you would write:

$$s^2 = t^n = stst = e$$

or simply list the words

$$s^2,\, t^n,\, stst$$

In this form, < Gens | Rels > = F(Gens)/N(Rels) where F(Gens) is the free group with Gens being its set of generators, and N(Rels) is the smallest normal subgroup of F(Gens) containing the elements of Rels.

-----------------------

Let f be an element of Aut(G). Prove that f is uniquely determined by:

a) whether or not it flips the number line
b) how many units it moves to the left or right

i.e. show that every automorphism is either left shift, right shift, flip then left shift, or flip then right shift. In addition, show that left shifts, right shifts, flip-then-left shifts and flip-then-right shifts are all automorphism. Then show that these four types of automorphism can be generated by the following three:

Flip about 0
Shift 1 to the right
Shift 1 to the left

In turn, realize each of these as products of s and t. This will complete the proof that Aut(G) = <s, t>, the subgroup of Aut(G) generated by s, and t.

----------------------------

Having shown that s and t generate Aut(G), you can check that <s, t| s², t²> presents that group by either figuring out N(Rels), then figuring out F(Gens)/N(Rels) and checking that the quotient is isomorphic to Aut(G). More simply, you just need to check that s² and t² are indeed relations of Aut(G), and that there are no more. Well you already know that those two are indeed relations. If there were any more, then they would be of the form x...ststst...y where x and y are either s or t (x and y can be different), and the word alternates. It's very very easy to prove that there are no relations like this.

 

[matt grime]

I guess that goes to show the problem with presentations. In my mind the group is clear Z sdp C_2, and you have a presentation as C_2*C_2, thus, if we are both correct, showing they are isomorphic groups, which is very unclear from the natural presentations of each.