Extending subsets to supersets in different ways

Question

We are given a collection of sets $A_1,\ldots,A_s$, pairwise different and each of cardinality $k$, and a collection of sets $B_1,\ldots,B_s$, pairwise different and each of cardinality $l>k+1$, such that $A_i\subseteq B_i$ for all $i=1,\ldots,s$. Can we find elements $a_i$ from $B_i\setminus A_i$ for all $i=1,\ldots,s$ such that the sets $A_i \cup \{a_i\}$ are all different?

Rephrasing this in terms of the corresponding subset lattice, this question is asking whether there are $s$ vertex-disjoint monotone paths between the sets $A_i$ and $B_i$, $i=1,\ldots,s$, in this graph.

I would be interested in knowing the answer to this question, or learning about related questions or references. Many thanks!

[Edit: It has been observed by Bjørn Kjos-Hanssen that the special case $l-k\geq s$ (="very few sets") is trivially true. Similarly, the special case $l-k\geq k+1$ (="set sizes differ a lot") can be easily proved by Hall's theorem. The first special case that falls outside these trivial ranges and that might therefore be interesting to consider is $k=2$ and $l=4$ (and $s\gg 1$).]

Answer 1

The answer is no. Here is a list of sets $A_i$ and $B_i$ which fails.

12, 1234
23, 1235
13, 1236
14, 1245
25, 2356
36, 1346
45, 1456
56, 2456
46, 3456

The failure can be seen by drawing the picture which consists of vertices for each $A_i$ and for each $A_i \cup j$ with $j\in B_i\setminus A_i$, and connecting $A_i$ to each $A_i \cup j$. This results in a bipartite graph, with the $A_i$ nodes having degree two. What we seek is a perfect matching in the graph. In the above example, the graph consists of three paths of length 6 between 123 and 456, and this graph has no perfect matching, so there is no solution.