著者

伊東 利哉 武井 由智 垂井 淳

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.194, pp.39-46, 1999-07-21

参考文献数

13

---

置換族がk点独立性を持つとは, 直観的には, そこから置換を一様ランダムに選んだとき任意の異なるk点が任意の異なるk点に等確率に写像されることである. 類似概念として, 任意の異なるk点の像のなす相対順序が等確率にあらわれるという性質が定義でき, これをk順位独立性と呼ぶことにする. また, 任意の異なる高々k点の像の中で全ての点が等確率で最小値となる性質がk制限最小値独立性として定義されている. 本論文では, 集合{0,1,...,n-1}に作用する置換族Cが上記各独立性を満足するときの要素数∥C∥の限界を考察し, 以下の結果一(1)下界: k制限最小値独立性は∥C∥≧n-1, k順位独立性は∥C∥≧(n/2)^<&lfloor;k/4&rfloor;> がそれぞれ必要(2)上界: k制限最小値独立置換族は∥C∥= o((en)^k), k順位独立置換族は∥C∥=0(n^<k2/(21nk)>)でそれぞれ構成可能を示す.