EC20.7-20.9_nishida

Extremal Combinatorics
20.7-20.9
B4 西田
尚平
20.7 Hashing functions
アルファベット
上の次
元のベクトルの集合を考える
 その中のどのk個を取ってきてもある
次元xが存在して、その次元によってk
個のベクトルはすべてdisjointとなる
 そんな集合Vはどのくらいまで要素を
持つことができるかを知りたい

20.7 Hashing functions
20.7 Hashing functions

要素数
れている
今回はこれを証明する
には上界が知ら
Lemma 20.8
Lemma 20.8
 アルファベット
、
上の次元のベクトルの集合 ,
を考える

のある要素ｖにおいてでない座標
の個数をとする

の平均をとおく
が成立
Lemma 20.8の証明
すべての次元においてそこから
個の番号のsubsetを
の中
から選び、これをとする
 あるUの要素ｖにおいて

上界の証明

n個の要素の中から重複を許してr個
とってきた場合、それらがすべて
disjointである確率は
であることが知られている
（Muirhheadの不等式より）
上界の証明

をVの中より選んだ
個のベク
トル集合とする。それ以外のベクトル
からランダムに選んだｖにおいて、
を
の中の要素がすべてdisjoint
の数とすると、その数の期待値は
となり、pigeonhole propertyよりその平均
は多くとも
となる
上界の証明

集合Uを
とし、Uに含
まれるベクトルは
上で定義されるものとする、そしてそ
の中に含まれるベクトルは先のに
一対一対応で生成され、が
において独立な時は
p番目に大きい要素であるとき、をｐ
とする
独立でないときは
とする
上界の証明

するとUなかのどんな部分集合
はある次元によって独立であり、それ
らの中に＊を含むものはない
以上よりUにLemma 20.8を適用
これを変形して式が得られる
20.8
Submodular complexity measure
劣モジュラーの複雑性を測る
 ある回路に対して複雑性を
とおき

を満たす関数群を扱えるものとする
20.8
Submodular complexity measure
Theorem 20.10
 先の条件を満たすn変数関数の族
おいて
が成立する
に
Theorem 20.10の証明

あるd変数関数においてそれを
からランダムに選ぶとする
ここで
とおくと
より
Theorem 20.10の証明

これを
より
に拡張する
Theorem 20.10の証明

両辺を足し合わせて
Theorem 20.10の証明

ここではn+1を超えないランダムな
関数あるので、それを一般のに置き
換える
ここで
より
20.9 Dicrepancy

をそれぞれn要素のsetとし、
とすると要素iのを
と定める。そのTの集合
においてある関数を定
める
20.9 Dicrepancy

ある関数
において
という関数を定める。
この関数は有用な応用例がある。
しかしこの関数の値を求めるのは容易
なことではない。
20.9 Dicrepancy

ここである集合(cube)を定義する。

このD上である関数を定義する
この関数の期待値を
とした時、次の定理が成立する
Theorem 20.11
Theorem 20.11
すべての関数
て以下の不等式が成り立つ
これを証明する
におい
Theorem 20.11の証明
Claim 20.12
すべての
が成立する
に対して
Claim 20.12の証明

あるランダムに選ばれたcubeにおいて
最後はCauchy-Schwarzより
Claim 20.12の証明
以上より
Claim 20.13

ある関数がTのような集合の入力に
おいて値が等しい時
証明：
より
Claim 20.14

すべてのに対して
かつ
となるような関数が存在する
Claim 20.14の証明

ある関数を以下のように決める

とおくと
はTの
characteristic functionになる
Claim 20.14の証明

ｘをランダムに取ると
そして
Claim 20.14の証明

Pigeonhole propertyより

よって
と選べば
Claim 20.14は成立する
Theorem 20.11の証明

以上を踏まえて
よって定理が証明された

Download Report