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$).]



Extending subsets to supersets in different ways
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. 


