近似的k-対独立置換族の構成

スポンサーリンク

概要

論文の詳細を見る
本論文ではε-近似k-対独立置換族のサイズの上界・下界に関して考察し,以下の結果を示す:(1)任意のε>0に対して,置換族F⊆S_nがε-近似k-対独立であるとき,ε<1ならば|F|≥n(n-1)…(n-k+1),一方ε≥1ならば|F|≥{n(n-1)…(n-k+1)}/(1+ε)が成り立つ;(2)任意のε>0に対して,|F|=O((klnn)/εn(n-1)…(n-k+1)))を満たすε-近似k-対独立置換族F⊆S_nが存在する;(3)任意のεと任意の整数n=P^m-1(p:素数;m:正整数)に対して,|F|=O(n(n-1)/ε)を満たす(多項式時間標本可能な)ε-近似2-対独立置換族F⊆S_nが構成可能である;(3)任意のεと任意の整数n=P^m(p: 素数; m: 正整数)に対して,|F|=O(n(n-1)(n-2)/ε)を満たす(多項式時間標本可能な)ε-近似3-対独立置換族F⊆S_nが構成可能である
社団法人電子情報通信学会の論文
2003-04-18

著者

関連論文

もっと見る

スポンサーリンク