MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 10月4日分まで、IACR ePrint 2012/562まで

_ 気になった論文：Invariance groups of finite functions and orbit equivalence of permutation groups (Eszter K. Horváth, Géza Makay, Reinhard Pöschel, Tamás Waldhauser, arXiv:1210.1015)

Which subgroups of the symmetric group Sn arise as invariance groups of n-variable functions defined on a k-element domain? It appears that the higher the difference n-k, the more difficult to answer this question. For k>=n, the answer is easy: all subgroups of Sn are invariance groups. We give a complete answer in the cases k=n-1 and k=n-2, and we also give a partial answer in the general case: we describe invariance groups when n is much larger than n-k. The proof utilizes Galois connections and the corresponding closure operators on Sn, which turn out to provide a generalization of orbit equivalence of permutation groups. We also present some computational results, which show that all primitive groups except for the alternating groups arise as invariance groups of functions defined on a three-element domain.