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.



Transversals and almost transversals of a finite family of sets
Here is a family of counterexamples with arbitrarily large $l$ in the case $m=n=2$:


$$T\_1 = {\*}111111\cdots1$$
$$T\_2 = 0{\*}11111\cdots1$$
$$T\_3 = 00{\*}1111\cdots1$$
$$T\_4 = 000{\*}111\cdots1$$
$$T\_5 = 0000{\*}11\cdots1$$
$$\cdots$$
$$T\_{l-1} = 00000\cdots0{\*}1$$
$$T\_{l} = 00000\cdots00{\*}$$


i.e. $T\_i$ has $0$'s at positions below $i$ and $1$'s at positions greater than $i$.
Suppose $T$ is a transversal lying $2$-locally in this partial transversal. The pair of indices $(1,2)$ forces the two first bits of $T$ to be $0$. Moreover, if the $i$'th bit of $T$ is $0$ for $i<l-1$, then the pair of indices $(i,i+1)$ forces the $(i+1)$'th bit of $T$ to be $0$ too. By induction the $l-1$'th bit of $T$ is $0$, and then the pair of indices $(l-1,l)$ yields a contradiction.


