Extremal Combinatorics 14.1 ~ 14.2

Presentation on theme: "Extremal Combinatorics 14.1 ~ 14.2"— Presentation transcript:

1 Extremal Combinatorics 14.1 ~ 14.2
14.1 The linear algebra background 14.2 Spaces of incidence vectors B4　藤田俊之

2 14. The Basic Method 14.1 The linear algebra background
　線形代数の考え方を基盤にしてベクトル空間の上界と属するベクトルの一次独立性を利用する 14.1 The linear algebra background 14.2 Spaces of incidence vectors Fisher’s inequality Inclusion matrices Disjointness matrices

3 14.1 The linear algebra background
体　として 右のように ベクトル　 を定義する 和とスカラー積

4 14.1 The linear algebra background
ベクトル　　　　　　の一次結合 空間　を　　　　　　が張る 一次従属、一次独立

5 14.1 The linear algebra background
次元・基底 　右のとき 　　　　　　が次元の最大値なので自明 Proposition 14.1 　　　　　　が一次独立ならば 次元　のとき　　　　が成り立つ

6 14.1 The linear algebra background
スカラー積（内積） 直交補空間 Proposition 14.2 有限次元の空間　と部分空間　　　　に対し が成り立つ

7 14.1 The linear algebra background
　m×n行列 行列とベクトルの積 とおくと .

8 14.1 The linear algebra background
行列のランク 行列の行ベクトルと 列ベクトルのランクは一致する

9 14.1 The linear algebra background
非斉次連立方程式 　解けるかどうかの判定 同値 斉次連立方程式 Proposition 14.3 　　　　　のときの　　　　 の解空間は 次元　　　　　　　なる　 の部分空間となる

10 14.1 The linear algebra background
ノルム Proposition 14.4 （Cauchy-Schwarzの不等式） 　　　　　　のベクトルに対し 　　　　　　　　　　　　　が成り立つ

11 14.1 The linear algebra background
一般の位置 moment curve 　一般の位置にあるベクトルを得る手法 　　　　　　で　　　　なるベクトルの集合 が一次独立のとき　　を構成するベクトルを 一般の位置にある　という

12 14.1 The linear algebra background
証明 　n個の相異なる要素 　　　　を並べたn×n行列　を作る 　　　　　　Vandermondeの行列式 Proposition 14.5 　　　　かつ　　　　としたとき 　 個のベクトル　　　の集合は一般の位置にある

13 14.2 Spaces of incidence vectors
族　 とそれに含まれる集合に対応したベクトルの 線形独立性を考え、集合の個数を求める Fisher’s inequality 　Fisherの不等式 Inclusion matrices 　Vapnik-Chervonenkis dimension（VC次元）に関連 Disjointness matrices 　互いに素

14 がどの に含まれるかの表を元に として一次結合をとる
Fisher’s inequality 　　　　　がどの　 に含まれるかの表を元に として一次結合をとる Theorem 14.6（Fisherの不等式） 　　　　　　：相異なる　　　　　 の部分集合 　　　　　　とすべての　　　に対し が成り立つとき　 1 2 3 4 5 A1 v1 A2 v2 A3 v3

15 証明続き を従属と仮定して矛盾を導く を代入した 従属のとき等式の最右辺は0ではない よって矛盾 一次独立なのでProp14.1が成立する
Fisher’s inequality 証明続き 　　　　　　を従属と仮定して矛盾を導く 　　　　　　　　　　　　　　　　を代入した 従属のとき等式の最右辺は0ではない よって矛盾 一次独立なのでProp14.1が成立する

16 Inclusion matrices 族　 を集合　　　　　　の部分集合からなるとす る．ある　　　　に対し　のすべての部分集合　 が　　　　　　となるような が存在するとき，この族を(n, k)-denseという Theorem 14.7 族　 が　　　　個以上のメンバーを持てば 　　　　　　　　(n, k)-dense である

17 14.2.2 Inclusion matrices 証明 としてサイズ まで の の部分集合を数え上げる． をメンバーとする． のとき行は
　　　　　　　　　　としてサイズ　　　まで の　の部分集合を数え上げる． をメンバーとする． 　　　のとき行は 一次独立ではない． 一次結合を考えた ときに0でない係数 が存在する M Y1 Y2 Y3 E1 1 E2 E3 E4

18 14.2.2 Inclusion matrices すべて0ではない係数の組が にお いて存在する．
すべて0ではない係数の組が　　　　　　　にお いて存在する． 　　　　を　　　　　となる最小濃度の集合とす る．上式より　　　　．包除の原理を用いて 　　　　　　　　　　　　　　　　　　∵ 　　　を除いて右辺は消え，両辺は　　　で一致． 左辺は空でない．すべての　　　 に　　　　　で

19 ． 次元 より列ベク トルは 個以上 となることを示したい
Inclusion matrices Lemma 14.8 　　　　　とする．　上の最大次数　　　　　　の多項式はk-閾値関数から少なくとも　　　入力異なっている 　　　　　． 次元　　　 より列ベク トルは　　　　個以上 となることを示したい M u1 u2 u3 a1 1 a2 a3 a4

20 a=bのときを除いて最終項は0． よってClaimが成り立ちLemmaも成り立つ
Inclusion matrices Claim 14.9 　　　，　　　　　　　　　　　　としたとき a=bのときを除いて最終項は0． よってClaimが成り立ちLemmaも成り立つ

21 14.2.3 Disjointness matrices
自然数　　　，要素nの集合Xとする． X上でk-disjointnessな0-1行列をD=D(n, k)とし， 最大サイズkのXの部分集合によって行と列に　 ラベル付けされているとする． A行B列のエントリDA,Bは次式で定義される フルランク　 が一次独立

22 14.2.3 Disjointness matrices
　　　 とする．　　　　　　をとると 次の多項式を 考える Theorem 14.10 k-disjointnessな行列Dはフルランクで，つまり

23 14.2.3 Disjointness matrices
　　かつ　　　 で　　　となる最大限のある もまた見つけられる． 　　　　　 と考えると多項式fにおいて代替に 　　　　　　となる．この操作のあと最初のt個 の変数(　　　　　)における非ゼロ多項式はター ム　　　　　を変化させない．よって，変数に 　　　　代入すると1となる多項式が得られる．

24 14.2.3 Disjointness matrices
しかしこのとき多項式fはb=(a1, …, at, 1, … ,1)を代 入したとき値１をとることを意味する．つまり 　　　　　　　　とおくと　　　 . なおかつ 　　　 　のときに　　　　，つまり　　　　　． はつまり　　　　 を意味する．