最適な最小値独立置換族の構成

概要

論文の詳細を見る
最小値独立置換族は, インターネット上に存在する多数の類似した文書の特定に有用であることが知られている.整数n>0に対し, 集合{1, 2, ..., n}上の置換族Cが最小値独立であるとは, 任意の(空でない)部分集合X⊆{1, 2, ..., n}と任意のx∈Xに対し, π∈Cを一様且つ無作為に選んだ場合, Pr{min{π(X)}=π(x)}=‖X‖^<-1>が成り立つことを言う.ただし, ‖A‖は有限集合Aの要素数を表すものとする.これまでに, 集合{1, 2, ..., n}上の最小値独立置換族に関して, 以下の結果-(1)任意の最小値独立置換族Cに対して, ‖C‖>1cm(n, n-1, ..., 2, 1)=e^<n-o(n)>;(2)‖C‖<4^nとなるような最小値独立置換族Cが存在する-が知られているが, ‖C‖=1cm(n, n-1, ..., 2, 1)を満たす最小値独立置換族Cの存在さらにその構成法は未解決であった.本論文では, 全ての整数n>0に対し, ‖F_n‖=1cm(n, n-1, ..., 2, 1)を満たす極小な最小値独立置換族F_nの構成法を与え, その詳細な解析を行なう.
社団法人電子情報通信学会の論文
1998-11-20