?

Log in

   Journal    Friends    Archive    Profile    Memories
 

Not a difficult problem, but it was on the exam I was invigilating… - Problem-A-Day

mathicDec. 12th, 2009 06:34 pm

Not a difficult problem, but it was on the exam I was invigilating and I thought it was cute.

If G and G' are graphs isomorphic to K_{n,n} (complete bipartite), how many isomorphisms are there from G to G'?

8 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:s3ld0n
Date:December 20th, 2009 03:32 pm (UTC)
(Link)
Somehow yeah, "cute" is the right word.
From:mathic
Date:December 20th, 2009 08:24 pm (UTC)
(Link)
Sadly, only 2 out of 100 got the right answer... less than 10 even had the right idea =/
From:s3ld0n
Date:December 20th, 2009 09:12 pm (UTC)
(Link)
Was this a course for math undergrads?
From:mathic
Date:December 20th, 2009 09:46 pm (UTC)
(Link)
Math and computer science.
From:s3ld0n
Date:December 20th, 2009 09:43 pm (UTC)
(Link)
Okay, welll rather than just agreeing and pronouncing the problem easy, I'll solve...

So, letting the disjoint sets of vertices be V1 and V2, we count n! permutations of V2, and n! permutations of V1 per permutation of V2. So if we only map V1 to V1 and V2 to V2, there are n!n! permutations. Then if we allow mappings from V1 to V2 and vice versa, either all elements of V1 are mapped to V2 (and vice versa) or none are, in which case there are another n!n! mappings.

So the answer is 2 n! n! automorphisms of K_n,n.
From:mathic
Date:December 20th, 2009 09:52 pm (UTC)
(Link)
Yep.

One of the most creative student 'solutions' ended with, "therefore G and G' cannot exist".
From:s3ld0n
Date:December 20th, 2009 10:03 pm (UTC)
(Link)
Sounds like the student is suffering an identity crisis.

:P
From:cheeser1
Date:March 26th, 2010 02:16 pm (UTC)
(Link)
Which, for the algebraically inclined, makes the automorphism group of Kn,n the semidirect product (Sn×Sn)C2, where those groups are the usual (symmetric and cyclic respectively) and the semidirect action is the involution (σ,τ)(τ,σ)