co.combinatorics - Counting colored rook configurations in the cube - when is it even?

This can be phrased as a problem concerning Latin squares. Eg. a "rook set" is equivalent to a Latin square. For example:

123       100 010 001
231  <->  001 100 010
312       010 001 100

A colouring of the Latin square is a partition of its entries (corresponding to a coloured rook set).

We can therefore readily construct colour profiles P with c=n² such that N(P)=1 (that is, by partitioning some Latin square into n² parts). But we can do much better...

A defining set is a partial Latin square with a unique completion. A critical set is a minimal defining set. Let scs(n) be the size of a smallest critical set for Latin squares of order n. From a Latin square L containing a critical set of size scs(n), we can choose a partition (i.e. a c-colouring) such that the entries in the critical set are in parts of size 1 and the remaining entries of L are in a single part. This also will give rise to a colour profile P in which N(P)=1. It has been shown that scs(n)≤n²/4 for all n. (see J. Cooper, D. Donovan and J. Seberry, Latin squares and critical sets of minimal size, Australasian J. Combin 4 (1991), 113–120.) Hence we can deduce that for some c<=n²/4+1 we have N(P)≡1 (mod 2). But with a more intelligent choice of the partition, we can do better...

In fact, we can use the constructions in Cooper et al. to construct a colour profile P with c=n for which N(P)=1. I will only be able to prove this by example here (but it should be clear it can be readily generalised): Partition the "back circulant" Latin square of order 6 as follows.

123456     100000   020000   003000   000000   000000   000456
234561     000000   200000   030000   000000   000000   004561
345612 <-> 000000 + 000000 + 300000 + 000000 + 000000 + 045612
456123     000000   000000   000000   000000   000000   456123
561234     000000   000000   000000   000004   000000   561230
612345     000000   000000   000000   000040   000005   612300

Now observe that the three colour profiles are:

100005  111003  111003
020004  011004  011004
003003  001005  001005
000204  000006  000006
000015  000105  000105
000006  000114  000114

Together these form P. Given P, we can observe that any Latin square of order 6 with colour profile P must contain the following partial Latin square:

123...
23....
3.....
......
.....4
....45

Which is a critical set -- and therefore admits a unique completion (that is, to the "back circulant" Latin square of order 6). Therefore, if c=n there exists a color profile P for which N(P)=1, not just N(P)≡1 (mod 2).

EDIT: I presented this problem to our research group at Monash and we improved the upper bound to c=1 (which was a bit surprising!). The idea came from the following critical set (call it C) of the back-circulant Latin square, which is related to the one above, but contains more entries than the one above (but this doesn't matter for this problem).

12345.
2345..
345...
45....
5.....
......

We observed that if every entry in the critical set above is assigned one colour, and the remaining entries another colour, then there is a unique Latin square with that colour profile. That is, we derive the colour profile from in the following way.

123456     12345.   .....6
234561     2345..   ....61
345612 <-> 345... + ...612
456123     45....   ..6123
561234     5.....   .61234
612345     ......   612345

which gives rise to the following colour profile P:

15   51   51
24   42   42
33   33   33
42   24   24
51   15   15
06   06   06

We can deduce that any Latin square with the colour profile P will, in fact, contain the critical set C. Hence, N(P)=1.

To see how we deduce the critical set from the colour profile, we note that for the first colour, it contains 5 entries in the first row and column, 4 entries in the second row and column, and so on (and the same for columns). This selection of cells can take only one shape -- that is, it is unique. Then placing the symbols 1..5 in it can only be achieved in one way (to preserve the Latin property).

Since this can be generalised for all n≥2, the answer to your question "what is the largest c such that for all colour profiles P, N(P)≡0 (mod 2)" is c=1.

EDIT 2: We also discussed at our research meeting the complexity side of the problem.

Instance: colour profile P

Question: is N(P)≥1?

In fact, there is an easy way to see that this problem is NP-complete, since (a) we can embed instances of the problem of partial Latin square completion in the above problem and (b) a Latin square together with its colouring can be used as a certificate.

The problem of partial Latin square completion was shown to be NP-complete in: C. J., Colbourn, The complexity of completing partial Latin squares, Discrete Appl. Math. 8 (1984), no. 1, 25--30.