wu :: forums
« wu :: forums - Automorphism group of a directed graph. »

Welcome, Guest. Please Login or Register.
Nov 14th, 2024, 12:15am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, Eigenray, SMQ, Grimbal, william wu, towr)
   Automorphism group of a directed graph.
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Automorphism group of a directed graph.  (Read 874 times)
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Automorphism group of a directed graph.  
« on: Dec 19th, 2006, 2:02pm »
Quote Quote Modify 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: male
Posts: 1948
Re: Automorphism group of a directed graph.  
« Reply #1 on: Dec 19th, 2006, 3:40pm »
Quote Quote Modify Modify

With or without Feit-Thompson?
IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Automorphism group of a directed graph.  
« Reply #2 on: Dec 19th, 2006, 7:30pm »
Quote Quote Modify 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
*****






    flamingdragon532
Email

Gender: male
Posts: 671
Re: Automorphism group of a directed graph.  
« Reply #3 on: Dec 19th, 2006, 10:06pm »
Quote Quote Modify Modify

lol, thats a great statement, I think I should start quoting it.  Wink Giving no credit to you of course.   Grin
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: male
Posts: 405
Re: Automorphism group of a directed graph.  
« Reply #4 on: Dec 20th, 2006, 9:28am »
Quote Quote Modify 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: male
Posts: 489
Re: Automorphism group of a directed graph.  
« Reply #5 on: Dec 20th, 2006, 1:55pm »
Quote Quote Modify Modify

Exactly, ecoist.  So, this statement and the Feit-Thompson theorem are EQUIVALENT.
IP Logged
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Automorphism group of a directed graph.  
« Reply #6 on: Jan 30th, 2007, 3:47pm »
Quote Quote Modify 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. Roll Eyes
 

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: male
Posts: 489
Re: Automorphism group of a directed graph.  
« Reply #7 on: Jan 30th, 2007, 4:23pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Automorphism group of a directed graph.  
« Reply #8 on: Jan 30th, 2007, 7:20pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board