Group Marriage Problem

Abstract

Let $G$ be a permutation group acting on $[n]=\{1,...,n\}$ and $\mathcal{V}=\{V_i:i=1,...,n\}$ be a system of $n$ subsets of $[n]$. When is there an element $g\in G$ so that $g(i)\in V_i$ for each $i\in [n]$? If such $g$ exists, we say that $G$ has a $G$-marriage subject to $\mathcal{V}$. An obvious necessary condition is the {\it orbit condition}: for any $\varnothing \ne Y\subseteq [n]$, ${\bigcup }_{y\in Y}{V}_y\supseteq Y^g=\{g(y):y\in Y\}$ for some $g\in 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 $C_n$ where $n\ge 4$, then $G$ satisfies the $(n-1)$-orbit condition subject to $\V$ if and only if $G$ has a $G$-marriage subject to $\mathcal{V}$.