Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

(A puzzle) The largest size cliques in n-grouping graphs

  1. Dec 1, 2009 #1
    (I apologize in advance for the abuse of the word "group" in this problem. It does not mean a group in the mathematical sense).

    Imagine you have n^2 objects that need to be grouped in n groups of size n each. Let's call one such arrangement an "n-grouping."

    You can create n-groupings in (n^2)!/(n!)^(n+1) ways (check me on this).

    Now suppose you have one of these n-groupings, G1, and you would like to find a "complementary" n-grouping, G2. What I mean by this is that every group in G2 has exactly 1 object from each group of G1 (and vice versa--I believe it provable that if G2 is complementary to G1, then G1 is complementary to G2--check me on this).

    Now, for any given any n-grouping G, there are (n!)^(n-1) complementary n-groupings (check me on this too).

    Now imagine a graph where all the n-groupings are vertices, and where there is an edge between two n-groupings if and only if the two n-groupings are complementary.

    My questions are:
    1) What is the size of the largest clique?
    2) How many such cliques are there?

    For n=2, there is only 1 clique--the whole graph of three vertices. (This seems obvious to me, but check me on this one too)
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted