Group Marriage Problem

الأصل · EN

Let G be a permutation group acting on [n]={1,..., n} and V={Vᵢ: i=1,..., n} be a system of n subsets of [n]. When is there an element g ∈ G so that g(i) ∈ Vᵢ for each i ∈ [n]? If such g exists, we say that G has a G-marriage subject to V. An obvious necessary condition is the orbit condition: for any = Y [n], ∈ Y Vy Yᵍ={g(y): y ∈ Y } for some g ∈ G. Keevash (J. Combin. Theory Ser. A 111(2005), 289--309) observed that the orbit condition is sufficient when G is the symmetric group ([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 alternating group ([n]) or the cyclic group Cₙ where n ≥ 4, then G satisfies the (n-1)-orbit condition subject to if and only if G has a G-marriage subject to V.