
#1
Sep1106, 02:02 AM

P: 867

I have a combinatorial graph with vertex set [itex]\mathbb{Z}[/itex] such that the set [itex]\{\{i,i+1\}\,:\,i\in\mathbb{Z}\}[/itex], 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 i1 and i+1.
As well as having this graph, I have been given two automorphisms [tex]s(i):=i[/tex] [tex]t(i):=i+1[/tex] 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: [tex](s\circ t) \circ s = s\circ (t\circ s)[/tex] and [tex](s\circ t)\circ t = s\circ (t \circ t)[/tex]. iii) Identity: This is easy, right? Is the identity automorphism simply [itex]s\circ s[/itex]? Or [itex]t\circ t[/itex]? Both composition automorphisms map i to i. Perhaps Im getting this confused with s(0) = 0? I dont 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? 



#2
Sep1106, 02:31 AM

Sci Advisor
HW Helper
P: 2,589

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}. 



#3
Sep1106, 02:55 AM

P: 867

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, [itex]i,j[/itex] are connected by an edge [itex]e_{i,j}[/itex] then [itex]a(i),a(j)[/itex] will be connected by an edge [itex]e_{a(i),a(j)}[/itex]. Is the correct? EDIT 2: So for example, [itex]a(i):=3i[/itex] 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, Im completely wrong. 



#4
Sep1106, 08:03 AM

P: 867

Automorphism Group
So basically I have to prove that given any automorphism [itex]a(i)[/itex] defined on the vertices of my graph, it can be specified as a composition of [itex]s,t,s^{1},t^{1}[/itex]. But what are [itex]s^{1},t^{1}[/itex]? They are the inverse automorphisms are they not? But s maps i to i which means that [itex]s^{1}[/itex] maps i to i, and [itex]t^{1}[/itex] maps i to i+1, so essentially [itex]s(i) = s^{1}(i)[/itex] and [itex]t(i) = t^{1}(i)[/itex].
If this reasoning is correct, then I only have 2 automorphisms with which to specifiy an aribtrary automorphism. 



#5
Sep1106, 08:23 AM

P: 867

ASIDE: This is starting to look like a very easy question. I understand that the automorphism group [itex]\mbox{Aut}G[/itex] 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:
[tex]a_1(i):=i+n[/tex] [tex]a_2(i):=i+n[/tex] where [tex]n \in \mathbb{Z}[/tex]. 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: [tex]a_3(i):=\lambda_1 i + \lambda_2\quad\lambda_1,\lambda_2 \in \mathbb{Z}[/tex] 



#6
Sep1106, 11:26 AM

Sci Advisor
HW Helper
P: 2,589

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.




#7
Sep1106, 11:30 AM

Sci Advisor
HW Helper
P: 9,398

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 i1) 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. 



#8
Sep1106, 08:24 PM

P: 867

[tex]s(i):i\mapsto i[/tex] [tex]s(i+1):i+1\mapsto i1[/tex] [tex]s(i1):i1\mapsto i+1[/tex] [tex]t(i):i\mapsto i+1[/tex] [tex]t(i+1):i+1\mapsto i[/tex] [tex]t(i1):i1\mapsto i+2[/tex] This shows where each vertex i and it's neighbours i+1 and i1 get mapped too. Should I be noticing something here? 



#9
Sep1106, 11:44 PM

P: 867

I do notice that
[tex](t\circ s)(i):=i+1[/tex] which I guess is the "shift" automorphism Matt was talking about. And then [tex](s\circ t)(i):=i1[/tex] which shifts vertices backward one vertex (all the while preserving edges because the composition is of the form i found earlier: [itex]\pm i +n[/itex], with [itex]n\in\mathbb{Z}[/itex]. 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 [itex](s\circ t)[/itex]'s. Does this sound right? EDIT: So for example, the following automorphism (yes, I believe it is an automorphism) [tex]\phi(i):=i+3[/tex] can be written as [tex]\phi(i) = (t\circ s)^3(i)[/tex] and [tex]\phi(i):=i3=(s\circ t)^3(i)[/tex] PS: What is a presentation of a group? 



#10
Sep1206, 01:01 AM

Sci Advisor
HW Helper
P: 9,398

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 2cycles in S_3 I'm trying to use as generators) 



#11
Sep1206, 03:12 AM

P: 867

How do you tell that the Gens and Rels constitute a presentation? I mean, how do you know that
[tex]D_n = \langle s,t\,\,s^2=t^n=e \wedge sts=t^{1}\rangle[/tex] is a presentation for the Dihedral group? Would [tex]\langle s,t\,\,s^2=t^2=1\rangle[/tex] 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 [itex]s^2=t^2=1[/itex] 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? 



#12
Sep1206, 01:01 PM

Sci Advisor
HW Helper
P: 9,398

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. 



#13
Sep1206, 01:01 PM

Sci Advisor
HW Helper
P: 2,589

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:
[tex]s^2 = t^n = e\wedge sts = t^{1}[/tex] you would write: [tex]s^2 = t^n = stst = e[/tex] or simply list the words [tex]s^2,\, t^n,\, stst[/tex] 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, flipthenleft shifts and flipthenright 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^{2}, t^{2}> 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^{2} and t^{2} 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. 



#14
Sep1206, 01:26 PM

Sci Advisor
HW Helper
P: 9,398

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.



Register to reply 
Related Discussions  
Cyclic automorphism group  Calculus & Beyond Homework  2  
Automorphism Group  Linear & Abstract Algebra  20  
Cyclic Automorphism Group  Linear & Abstract Algebra  1  
Automorphism group of field extension  Calculus & Beyond Homework  1  
group of automorphism of S3  Calculus & Beyond Homework  3 