Subsets and partitions

There are several packing and covering problems for subsets of a set, which have been worked over by many people. For example, given t, k and n, how many k-subsets of an n-set can we pack so that no t-subset is contained in more than one of them? How many k-subsets do we need to ensure that we have included every t-set in at least one? And when can we achieve both goals simultaneously? The last problem, going back to Kirkman, is the one that has been solved for all sufficiently large n (in terms of t and k) by Peter Keevash.

There is another sort of packing and covering problem associated with subsets and partitions, which crops up in various places in semigroup theory. Given k and n, the relationship between a k-set S and a k-partition P (a partition with k parts), the relationship we are interested in is that the subset is a transversal, or section, for the partition; that is, there is just one of its elements in each part of the partition.

So we can ask questions like: what is the least number of k-subsets we need to ensure that we have a transversal for every k-partition? Dually, what is the least number of k-partitions we need so that every subset is a transversal for at least one of them? (These are the covering problems.) How many subsets can we have if no two of them are transversals for the same partition? And dually? (These seem much more speculative problems.) And is there an exact version? (This seems quite unlikely.)

The connection with semigroup theory is easily explained. A transformation of rank k of an n-set has image a k-set, and kernel a k-partition. (The kernel of a map is the partition where two points are in the same part if they have the same image.) Now if two transformations of rank k are composed, the product has rank k if and only if the image of the first transformation is a transversal for the kernel of the second.

The first of these questions, the minimum size of a set of k-sets containing a transversal to every k-partition, is the subject of a paper by Csilla Bujtás and Zsolt Tuza in Graphs and Combinatorics 25 (2009), 807-816 (the paper is here). In brief: there are trivial upper and lower bounds for this nmber, as functions of n and k: they show that, for k fixed or small compared to n, the lower bound is near the truth. As they remark, interesting things happen when k is close to n.

This connection leads us to several variants, some of which we have results about. For example, which permutation groups G on the n-set have the property that every orbit on k-sets contains a transversal to every partition? Which have the property that some orbit on k-sets contains a transversal to every partition? If we can’t do this with a single orbit of a group, what is the fewest number of orbits required?

For example, consider k=2. A collection of 2-sets contains a transversal to every 2-partition if and only if it is the edge set of a connected graph. So every orbit of a group G on 2-sets contains transversals to all 2-partitions if and only if all the orbital graphs for G are connected, or equivalently G is primitive (as discussed here). On the other hand, no orbit contains transversals to all 2-partitions if and only if all orbital graphs are disconnected. I haven’t seen a name for this property; it would seem natural to call such a group fully imprimitive. The property that every orbit on k-sets contains transversals to every k-partition is discussed for arbitrary k in this paper.

And semigroup theory also leads us to a “complementary” problem: Find a large set of k-sets and a large set of k-partitions such that none of the sets is a transversal for any of the partitions. There are several strategies for doing this, and it is not clear which will give the strongest result for the semigroup problem.

I will probably report further on some of these problems shortly …