2009/12/22 by Cheng Yeaw Ku, Ku, Cheng Yeaw, Kok Bin Wong +1
Social Sciences · #Combinatorics (math.CO) #FOS: Mathematics #Names, Identity, and Discrimination Research
paper · pdf · doi:10.48550/arxiv.0912.4443
openalex publication_date 2009/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 g exists, we say that G has a G-marriage subject to V. An obvious necessary condition is the \it orbit condition: for any ∅ \not = Y ⊆ [n], \bigcupy ∈ Y Vy ⊇ Yg=\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 \Sym([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 \Alt([n]) or the cyclic group Cn where n ≥ 4, then G satisfies the (n-1)-orbit condition subject to \V if and only if G has a G-marriage subject to V.