The group marriage problem

Let G be a permutation group acting on [n]={1,…,n} and V={Vi:i=1,…,n} be a system of n subsets of [n]. When is there an element g∈G so that g(i)∈Vi for each i∈[n]? If such a g exists, we say that G has a G-marriage subject to V. An obvious necessary condition is the orbit condition: for any nonempty subset Y of [n], there is an element g∈G such that the image of Y under g is contained in ⋃y∈YVy. Keevash observed that the orbit condition is sufficient when G is the symmetric group Sn; this is in fact equivalent to the celebrated Hall's Marriage Theorem. We prove that the orbit condition is sufficient if and only if G is a direct product of symmetric groups. We extend the notion of orbit condition to that of k-orbit condition and prove that if G is the cyclic group Cn where n⩾4 or G acts 2-transitively on [n], then G satisfies the (n−1)-orbit condition subject to V if and only if G has a G-marriage subject to V.