The group marriage problem |
| |
Authors: | Cheng Yeaw Ku |
| |
Institution: | a Department of Mathematics, National University of Singapore, Singapore 117543, Singapore b Institute of Mathematical Sciences, University of Malaya, 50603 Kuala Lumpur, Malaysia |
| |
Abstract: | 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 ?y∈YVy. Keevash observed that the orbit condition is sufficient when G is the symmetric group Sn; 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 Cn 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. |
| |
Keywords: | Hall's marriage problem Permutation group Orbit condition |
本文献已被 ScienceDirect 等数据库收录! |
|