The group marriage problem

Let G be a permutation group acting on [ n ] = { 1 , … , n } and V = { V i : i = 1 , … , n } be a system of n subsets of [ n ] . When is there an element g ∈ G so that g ( i ) ∈ V i 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 ∈ Y V y . Keevash observed that the orbit condition is sufficient when G is the symmetric group S n ; 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 C n 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 .