Author |
Topic: Automorphism group of a directed graph. (Read 868 times) |
|
Obob
Senior Riddler
Gender: 
Posts: 489
|
 |
Automorphism group of a directed graph.
« on: Dec 19th, 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 19th, 2006, 3:40pm » |
Quote Modify
|
With or without Feit-Thompson?
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Automorphism group of a directed graph.
« Reply #2 on: Dec 19th, 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 19th, 2006, 7:32pm by Obob » |
IP Logged |
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: Automorphism group of a directed graph.
« Reply #3 on: Dec 19th, 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 20th, 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 20th, 2006, 9:51am by ecoist » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Automorphism group of a directed graph.
« Reply #5 on: Dec 20th, 2006, 1:55pm » |
Quote Modify
|
Exactly, ecoist. So, this statement and the Feit-Thompson theorem are EQUIVALENT.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Automorphism group of a directed graph.
« Reply #6 on: Jan 30th, 2007, 3:47pm » |
Quote Modify
|
Just to clarify, is this the expected solution? I make liberal use of Feit-Thompson, 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 F-T.
|
|
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 30th, 2007, 4:23pm » |
Quote Modify
|
Yes, that is correct Pietro. The interesting thing is that Feit-Thompson 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 30th, 2007, 7:20pm » |
Quote Modify
|
Of course, since Feit-Thompson is a theorem, every other theorem is equivalent to it. You can prove this without using Feit-Thompson, but essentially you do this by building the proof of Feit-Thompson inside your own proof.
As a side-point, 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 30th, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print