Skip to main content
3 of 3
The index l was in fact correct. n is the bound on the size of each S_i.

Transversals and almost transversals of a finite family of sets

The following is a purely combinatorial problem that I came across in the course of research in non-classical logic. It sounds to me like the kind of question that someone may very well have considered at some point, but not being a very combinatorially minded person myself, I have not managed to find it in the literature. Both a positive and a negative answer to the question below, or pointers to some relevant literature, would be of interest to me. For all I know, this may be a piece of cake to a combinatorialist. I should say that I have no particular reason to suspect that the answer should be positive (although I secretly hope against hope that it might be).

Consider a family of disjoint sets $S_1, \dots, S_l$ where each $S_i$ has cardinality at most $n$. A transversal is a set $T$ which contains exactly one element from each of these sets (and nothing else). An $i$-transversal is a set $T_i$ which contains exactly one element from each of these sets except for the set $S_i$ (and nothing else). In particular, transversals have exactly $l$ elements, while $i$-transversals have exactly $l-1$ elements. An almost tranversal family is an $l$-tuple $(T_1, \dots, T_l)$ such that each of these sets $T_i$ is an $i$-transversal. A transversal $T$ lies $m$-locally in this family if each subset of $T$ of cardinality $m$ is a subset of some $T_i$.

Question. Given $n \geq 2$ and $m \geq 2$, is it the case that for each such family of disjoint sets $S_1, \dots, S_l$ with large enough $l$ and each almost transversal family $(T_1, \dots, T_l)$ over these sets one can find a transversal $T$ which lies $m$-locally in $(T_1, \dots, T_l)$?

Already the case of $n = m = 2$ would be of interest to me. In that case, a transversal corresponds to a binary string of length $l$, and an almost transversal family corresponds to an $l$-tuple of binary strings of length $l-1$. More suggestively, an almost transversal family corresponds to an $l$-tuple of strings $T_i$ of length $l$ where all the symbols of $T_i$ except for the $i$-th symbol are 0 or 1, for example, $({*}1100, 0{*}110, 10{*}10, 110{*}1, 1010{*})$. The transversal $10100$ then lies $2$-locally in this almost transversal family: whenever we pick any pair of positions in $10100$, there is an almost transversal in our family which agrees with $10100$ on these two positions. For small values of $l$ one can certainly find almost transversal families which have no $2$-local transversal. Still, it is less than clear to me whether counter-examples of arbitrarily high length exist.