最小値独立置換族と3点独立置換族

概要

論文の詳細を見る
最小値独立置換族は, インターネット上に存在する多数の類似した文書の特定に有用であることが知られている.任意の整数n0に対し, 集合{0, 1, ..., n-1}上の置換全体をS_nとするとき, 置換族F⊆S_nが最小値独立であるとは, 任意の(空でない)部分集合X⊆{0, 1, ..., n-1}と任意のx∈Xに対し, π∈Fを一様且つ無作為に選んだ場合, Pr_<π∈F>[min{π(X)}=π(X)]=‖X‖^<-1>が成り立つことを言う(ただし, ‖A‖は有限集合Aの要素数を表すものとする).一方, 任意の整数d≥1に対し, 置換族F⊆S_nがd点独立であるとは, 任意の異なるx_1, x_2, ..., x_d∈{0, 1, ..., n-1}と任意の異なるy_1, y_2, ..., y_d∈{0, 1, ..., n-1}に対し, π∈Fを一様且つ無作為に選んだ場合, Pr_<π∈F>[Λ^d_<i=1>π(x_i)=y_i]=1/{n(n-1)・・・(n-d+1)}が成り立つことを言い, d=2, 3に対してのみ、非自明な-対称群あるいは交代群とは異なる-d点独立置換族の構成法が知られている.これまでに, Broderらによって, 任意の2点独立置換族F⊆S_nの振舞は, 最小値独立置換族の振舞を概ね良好に近似する-任意のX⊆{0, 1, ..., n-1}と任意のx∈Xに対して, 3≤‖X‖=k≤n-2とすると, (下界)Pr_<π∈F>[min{π(X)}=π(x)]≥1/{2(k-1)};(上界)Pr_<π∈F>[min{π(X)}=π(x)]≤2/√<k>-3/(2k)-ことが示されている.本論文では, これを3点独立置換族に拡張し, 任意の3点独立置換族F⊆S_nの振舞は, 最小値独立置換族の振舞をより良好に近似する-任意のX⊆{0, 1, ..., n-1}と任意のx∈Xに対して, 4≤‖X‖=k≤n-3とすると, (下界)Pr_<π∈F>[min{π(X)}=π(x)]≥1/{2(k-2)}-1/{6(k-2)^2};(上界)Pr_<π∈F>[min{π(X)}]≤2/√<k>-2/k+1(3k√<k>)-ことを示す.
2000-10-20

最小値独立置換族と3点独立置換族

スポンサーリンク

概要

著者

関連論文

スポンサーリンク