Author 
Topic: Automorphism group of a directed graph. (Read 874 times) 

Obob
Senior Riddler
Gender:
Posts: 489


Automorphism group of a directed graph.
« on: Dec 19^{th}, 2006, 2:02pm » 
Quote Modify

A tournament on n vertices is some orientation of the edges of the complete graph on n vertices. So for any two vertices v and w, exactly one of v>w or w>v holds (we write v>w to mean there is a directed edge from v to w). An automorphism of a directed graph is a bijection of the vertices which preserves the oriented edges. Prove that the automorphism group of a tournament is solvable.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Automorphism group of a directed graph.
« Reply #1 on: Dec 19^{th}, 2006, 3:40pm » 
Quote Modify

With or without FeitThompson?


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Automorphism group of a directed graph.
« Reply #2 on: Dec 19^{th}, 2006, 7:30pm » 
Quote Modify

That's a good question, Eigenray. So good, in fact, that I invite you to answer it yourself.

« Last Edit: Dec 19^{th}, 2006, 7:32pm by Obob » 
IP Logged 



flamingdragon
Uberpuzzler
Gender:
Posts: 671


Re: Automorphism group of a directed graph.
« Reply #3 on: Dec 19^{th}, 2006, 10:06pm » 
Quote Modify

lol, thats a great statement, I think I should start quoting it. Giving no credit to you of course.


IP Logged 
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphism group of a directed graph.
« Reply #4 on: Dec 20^{th}, 2006, 9:28am » 
Quote Modify

My opinion is worth what you are paying for it, but I suspect there is no "high school" solution. For, given any group G of odd order, there are tournaments T (with both even and odd numbers of vertices) whose automorphism group contains G.

« Last Edit: Dec 20^{th}, 2006, 9:51am by ecoist » 
IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Automorphism group of a directed graph.
« Reply #5 on: Dec 20^{th}, 2006, 1:55pm » 
Quote Modify

Exactly, ecoist. So, this statement and the FeitThompson theorem are EQUIVALENT.


IP Logged 



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Automorphism group of a directed graph.
« Reply #6 on: Jan 30^{th}, 2007, 3:47pm » 
Quote Modify

Just to clarify, is this the expected solution? I make liberal use of FeitThompson, which alas, despite some promising false starts, I have been unable to prove in the last couple of days. I claim that the automorphism group G of any tournament T has odd order. Suppose G has even order. Then there is an f in G of order 2 (Sylow). That is, f != id and f^2 = id. Since f != 1, there must be a vextex u of T which f moves. Let f(u) = v. Then f(v) = u. But this reverses the direction of the arrow between u and v, which is incompatible with the definition of graph automorphism. Therefore G has odd order, and is solvable by FT.


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



Obob
Senior Riddler
Gender:
Posts: 489


Re: Automorphism group of a directed graph.
« Reply #7 on: Jan 30^{th}, 2007, 4:23pm » 
Quote Modify

Yes, that is correct Pietro. The interesting thing is that FeitThompson is essentially necessary for the proof.


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Automorphism group of a directed graph.
« Reply #8 on: Jan 30^{th}, 2007, 7:20pm » 
Quote Modify

Of course, since FeitThompson is a theorem, every other theorem is equivalent to it. You can prove this without using FeitThompson, but essentially you do this by building the proof of FeitThompson inside your own proof. As a sidepoint, beyond Eigenray's initial post, hiding the text is fairly pointless. Everyone who reads that far down is going to be highlighting any hidden text.

« Last Edit: Jan 30^{th}, 2007, 7:22pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



