Extremal Combinatorics 14.1 ~ 14.2 14.1 The linear algebra background 14.2 Spaces of incidence vectors B4 藤田俊之 14. The Basic Method 線形代数の考え方を基盤にしてベクトル空間の 上界と属するベクトルの一次独立性を利用する 14.1 The linear algebra background 14.2 Spaces of incidence vectors 14.2.1 Fisher’s inequality 14.2.2 Inclusion matrices 14.2.3 Disjointness matrices 14.1 The linear algebra background 体 として 右のように ベクトル を定義する 和とスカラー積 14.1 The linear algebra background ベクトル の一次結合 空間 を が張る 一次従属、一次独立 14.1 The linear algebra background 次元・基底 右のとき Proposition 14.1 が一次独立ならば 次元 のとき が成り立つ が次元の最大値なので自明 14.1 The linear algebra background スカラー積（内積） 直交補空間 Proposition 14.2 有限次元の空間 と部分空間 が成り立つ に対し 14.1 The linear algebra background m×n行列 行列とベクトルの積 とおくと . 14.1 The linear algebra background 行列のランク 行列の行ベクトルと 列ベクトルのランクは一致する 14.1 The linear algebra background 非斉次連立方程式 解けるかどうかの判定 同値 斉次連立方程式 Proposition 14.3 のときの 次元 なる の解空間は の部分空間となる 14.1 The linear algebra background ノルム Proposition 14.4 （Cauchy-Schwarzの不等式） のベクトルに対し が成り立つ 14.1 The linear algebra background 一般の位置 で なるベクトルの集合 が一次独立のとき を構成するベクトルを 一般の位置にある という moment curve 一般の位置にあるベクトルを得る手法 14.1 The linear algebra background Proposition 14.5 かつ 個のベクトル としたとき の集合は一般の位置にある 証明 n個の相異なる要素 を並べたn×n行列 を作る Vandermondeの行列式 14.2 Spaces of incidence vectors 族 とそれに含まれる集合に対応したベクトルの 線形独立性を考え、集合の個数を求める 14.2.1 Fisher’s inequality Fisherの不等式 14.2.2 Inclusion matrices Vapnik-Chervonenkis dimension（VC次元）に関連 14.2.3 Disjointness matrices 互いに素 14.2.1 Fisher’s inequality Theorem 14.6（Fisherの不等式） ：相異なる の部分集合 とすべての に対し が成り立つとき がどの に含まれるかの表を元に として一次結合をとる 1 2 3 4 5 A1 1 1 0 0 0 v1 A2 0 1 0 1 0 v2 A3 1 0 1 0 1 v3 14.2.1 Fisher’s inequality 証明続き を従属と仮定して矛盾を導く を代入した 従属のとき等式の最右辺は0ではない よって矛盾 一次独立なのでProp14.1が成立する 14.2.2 Inclusion matrices 族 を集合 の部分集合からなるとす る．ある に対し のすべての部分集合 が となるような が存在するとき，この族を(n, k)-denseという Theorem 14.7 族 が 個以上のメンバーを持てば (n, k)-dense である 14.2.2 Inclusion matrices 証明 としてサイズ の の部分集合を数え上げる． をメンバーとする． M Y1 のとき行は E1 1 一次独立ではない． E2 1 E3 1 一次結合を考えた E4 1 ときに0でない係数 が存在する まで Y2 Y3 0 0 1 0 1 1 1 1 14.2.2 Inclusion matrices すべて0ではない係数の組が にお いて存在する． を となる最小濃度の集合とす る．上式より ．包除の原理を用いて ∵ を除いて右辺は消え，両辺は 左辺は空でない．すべての に で一致． で 14.2.2 Inclusion matrices Lemma 14.8 とする． 関数から少なくとも 上の最大次数 入力異なっている ． 次元 より列ベク トルは 個以上 となることを示したい の多項式はk-閾値 M u1 u2 u3 a1 1 0 0 a2 1 1 0 a3 1 1 1 a4 1 1 1 14.2.2 Inclusion matrices Claim 14.9 ， としたとき a=bのときを除いて最終項は0． よってClaimが成り立ちLemmaも成り立つ 14.2.3 Disjointness matrices 自然数 ，要素nの集合Xとする． X上でk-disjointnessな0-1行列をD=D(n, k)とし， 最大サイズkのXの部分集合によって行と列に ラベル付けされているとする． A行B列のエントリDA,Bは次式で定義される フルランク が一次独立 14.2.3 Disjointness matrices . Theorem 14.10 k-disjointnessな行列Dはフルランクで，つまり とする． 次の多項式を 考える をとると 14.2.3 Disjointness matrices より，少なくともひとつλIはゼロでない． かつ で となる最大限のある もまた見つけられる． と考えると多項式fにおいて代替に となる．この操作のあと最初のt個 の変数( )における非ゼロ多項式はター ム を変化させない．よって，変数に 代入すると1となる多項式が得られる． 14.2.3 Disjointness matrices しかしこのとき多項式fはb=(a1, …, at, 1, … ,1)を代 入したとき値１をとることを意味する．つまり とおくと . なおかつ のときに ，つまり はつまり を意味する． ．
© Copyright 2024 ExpyDoc
