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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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

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