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 U _(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.