Transversals and almost transversals of a finite family of sets

Question

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.

Answer 1

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.