- #1

ygolo

- 30

- 0

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)