A little about covering arrays, some independent sets and a graph core

Mike Newman

Abstract

Let X be the graph whose vertex set is the partitions of {1..9} into 3 cells of size 3. Vertices are adjacent when their partitions are skew, that is each cell of one partition intersects each cell of the other. More generally, we have the graphs X(n,k) whose vertex set is the partitions in {1..n} into k cells of size at least k, adjacency meaning skew.

These graphs are important because there exists an (G,k,n) covering array if and only if G maps homomorphically into X(n,k). Without even saying what a covering array is, we are motivated to ask whether X(n,k) is a core?

Using the eigenspaces of X(9,3), we can characterize all the maximum independent sets; from this it follws that X(9,3) is a core. The fact that this graph sits in an association scheme is useful, but perhaps not essential.

This leaves some interesting questions. As a byproduct, we determine that the chromatic number is 5 or 6. The computer says 6, but it seems there should be a nicer proof of this.

Also, much, but not all, of our arguments apply more generally, but we can't (yet) prove that X(k^2,k) is a core, nor what it's chromatic number is, nor characterize its maximum independent sets. There are "obviously correct answers" to these questions, but it would be nice to have some proofs of them. Suggestions welcomed!

Time permitting, I might define "covering array", and "association scheme".