wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Automorphism group of a directed graph.
        
(Message started by: Obob on Dec 19^th, 2006, 2:02pm)

Title: Automorphism group of a directed graph.
Post by Obob on Dec 19^th, 2006, 2:02pm

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.

Title: Re: Automorphism group of a directed graph.
Post by Eigenray on Dec 19^th, 2006, 3:40pm

With or without [hide]Feit-Thompson[/hide]?

Title: Re: Automorphism group of a directed graph.
Post by Obob on Dec 19^th, 2006, 7:30pm

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

Title: Re: Automorphism group of a directed graph.
Post by flamingdragon on Dec 19^th, 2006, 10:06pm

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

Title: Re: Automorphism group of a directed graph.
Post by ecoist on Dec 20^th, 2006, 9:28am

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

Title: Re: Automorphism group of a directed graph.
Post by Obob on Dec 20^th, 2006, 1:55pm

Exactly, ecoist. So, [hide]this statement and the Feit-Thompson theorem are EQUIVALENT.[/hide]

Title: Re: Automorphism group of a directed graph.
Post by Pietro K.C. on Jan 30^th, 2007, 3:47pm

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

[hide]
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.
[/hide]

Title: Re: Automorphism group of a directed graph.
Post by Obob on Jan 30^th, 2007, 4:23pm

Yes, that is correct Pietro. The interesting thing is that [hide]Feit-Thompson is essentially necessary for the proof.[/hide]

Title: Re: Automorphism group of a directed graph.
Post by Icarus on Jan 30^th, 2007, 7:20pm

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.