11
$\begingroup$

Informal Statement

In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,k)$ if and only if $i+j+k=0\mod n$. In general, there are "many" ways to do this.

Each such "attack-free" rook position can be colored with $c$ colors. When we fix an $i$, we can then count the colors in the matrix $(i,.,.)$, and can do similarly for each $j$ and $k$. Call this set of tuples of colors-counts the "color profile". For each color profile, there is either an even or odd number of colored rook positions that achieve it. I want to know the largest $c$ such that all color profiles have an even number of colored rook positions achieving it. In particular, I want to say that $c=\omega(n)$. This question came up in some complexity theory research, but the question seems interesting in its own right.


Formal Statement

Define $[n]$ to be the set ${1,\ldots, n}$, and define $[n]^3=[n]\times[n]\times[n]$. Define a $c$-coloring of a set $S\subseteq[n]^3$ to be a function $C:S\to[c]$. We can say that this is a $c$-coloring of $[n]^3$ with the convention that $C(i,j,k)=0$ for $(i,j,k)\notin S$. A $c$-coloring $C$ induces a color profile $P$, which is a function from $P:[n]\times[3]\times[c]\to[n]$, via the rules

  • $P(i,1,c)$ is the number of $(j,k)\in[n]^2$ such that $C(i,j,k)=c$.

  • $P(j,2,c)$ is the number of $(i,k)\in[n]^2$ such that $C(i,j,k)=c$.

  • $P(k,3,c)$ is the number of $(i,j)\in[n]^2$ such that $C(i,j,k)=c$.

where we keep in mind the convention above on $(i,j,k)\notin S$.

Call a set $S\subseteq [n]^3$ to be a rook set, if

  • for all $i,j\in[n]$, there is exactly one $k\in[n]$ such that $(i,j,k)\in S$

  • for all $j,k\in[n]$, there is exactly one $i\in[n]$ such that $(i,j,k)\in S$

  • for all $i,k\in[n]$, there is exactly one $j\in[n]$ such that $(i,j,k)\in S$

Let a colored rook set $C_S$ correspond the coloring $C$ of a rook set $S$.

Define $N(P)$ to be the number of colored rook sets $C_S$ that induce the color profile $P$.

The question is:

For each fixed $n$, what is the largest $c$ such that for all color profiles $P$, $N(P)\equiv 0\mod 2$? In particular, is the largest $c$ asymptotically $\omega(n)$?


What I know

It should be clear that this problem can be defined analogously in any dimension, and I'm interested in this more general question. I state it with $d\ge3$ because I can solve the $d=2$ case exactly. In particular

For each $n$, for any $c\le n-1$, and any color profile $P$ on grid $[n]^2$, $N(P)\equiv 0 \mod 2$. For $c\ge n$, there are profiles $P$ where $N(P)\equiv 1\mod 2$.

This can be proven by exhibiting a bijection between colored rook sets (which in d=2 are just permutation matrices). Specifically, using the pigeonhole principle $c\le n-1$ implies that there are two rooks with the same color. If they were at positions $(i,j)$ and $(i',j')$, then we replace them with the rooks of the same color at positions $(i,j')$ and $(i',j)$. (Of course, one needs to make this well-defined to ensure a bijection.)


Possible Methods

I see two possible methods of proof

  • generalize the above bijection proof to the 3-dimensional case

    • I don't know how to use the pigeonhole principle to get such an extension, but it seems possible that there is a method to show that some motif exists in any colored rook set, and then argue that we can alter this motif to get the bijection
  • define a system of polynomials (over $\mathbb{F}_2$) such that the solution set corresponds to exactly the colored rook sets inducing a color profile $P$. Then try to apply the Chevalley-Warning theorem.

    • I've tried this, but can't seem to get systems of polynomials where the sum of the total degrees is strictly less than the number of variables, so the C-W theorem does not apply.
    • One can observe the the C-W theorem is an "iff" here: if $N(P)$ is even then there is a multilinear polynomial with degree strictly less than the number of variables, such that the solution set encodes those $C_S$'s that induce $P$.
  • Instead of using "rook sets", one can ask the question for other classes of subsets of $[n]^3$. I'd be happy with establishing $c=\omega(n)$ for any class of subsets (although I'd like to be able to compute at least one example of such a subset efficiently).

Are there other methods for counting modulo two that I missed?

$\endgroup$
1
  • $\begingroup$ By the way, the codomain of P should include 0. $\endgroup$ Mar 6, 2010 at 10:38

1 Answer 1

13
$\begingroup$

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=n2 such that N(P)=1 (that is, by partitioning some Latin square into n2 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)≤n2/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<=n2/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.

$\endgroup$
2
  • $\begingroup$ Ah, this seems to answer the most well-defined aspect of my question, though I'll have to take some more time later to fully digest this. I'm not sure if I should mark my question as "answered" as I'll comment more on the broader question I have. $\endgroup$
    – miforbes
    Mar 6, 2010 at 21:01
  • $\begingroup$ I suppose the remains of the question are too open-ended, so I'll mark this answer as the one I'm happy with. As for the c=n-1 case, I would imagine that for all $P$, $N(P)\equiv 0\mod 2$, but don't have any good reason to think this. However, I'm really looking for $c=\omega(n)$, (see my expanded section on the original motivation), so the $c=n-1$ case is slightly less interesting to me. $\endgroup$
    – miforbes
    Mar 6, 2010 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.