14. The Basic Method M1 太田圭亮 14.3 Spaces of polynomials 14.4 Combinatorics of linear spaces 14.5 The flipping cards game M1 太田圭亮

14.3 Spaces of polynomials 集合の要素数を線形代数の手法を用い てバウンドする． 要素と対応させたベクトルが線形独立 ならば，そのベクトルが存在する次元 でバウンドできる． Proposition14.2 m次元ベクトル空間に存在する が線形独立⇒

14.3 Spaces of polynomials 集合の要素を多項式に対応させる． その多項式が関数空間の線形独立な要 素であることを示す． polynomial techniqueとして知られる． 多くの応用があるが，それらは次のシ ンプルで強力な補題に基づいている．

Lemma 14.11 に対して関数 と要素 が以下を満たすとする． (a) (b) このとき， は 空間 の線形 独立な要素である．　

Lemma 14.11 証明 線形従属を仮定し，矛盾を導く． に対して である最小の を選び， を各 変数に代入． である最小の を選び， を各 変数に代入． よって ．これは(a)に矛盾．

14.3.1 Two-distance sets を 上の点とする． 各 間の距離が全て等しいならば， となる． を 上の点とする． 各 間の距離が全て等しいならば， 　 となる． 条件を緩め，各 間の距離の取り得 る値が2つのとき， はどうバウンド できるか？ このような集合を2-距離集合という．

14.3.1 Two-distance sets Theorem 14.12 証明 2-距離集合の要素数 集合の要素数を ，各2点間の距離が または であるとする． 各点 を次の多項式 に対応させる．

14.3.1 Two-distance sets 証明続き Lemma14.11より，各 は線形独立 各 が存在するベクトル空間を考える． 各 が存在するベクトル空間を考える． Lemma14.11 ⇒各 は線形独立

14.3.1 Two-distance sets 証明続き 各 は次の多項式の線形結合で表わせる． これらの数は， 各 は次の多項式の線形結合で表わせる． これらの数は， よって，各 が属する空間の次元は高々 ．よって

14.3.2 Sets with few intersection sizes Fisherの不等式を拡張する． Fisherの不等式（14.2.1） を の異なる部分 集合とする． 全ての に対して このとき， の部分を緩和する．

14.3.2 Sets with few intersection sizes 定義：L-intersecting 要素集合の部分集合族 がL-intersecting であるとは，整数の有限集合 があるとき， の任意の異なる要素A，B に対して であることをいう． のとき，Fisherの不等式． が与えられたとき， に関して何 が言えるか？

14.3.2 Sets with few intersection sizes がuniformのとき， 一般には以下の定理が成り立つ． Theorem 14.13 族 がL-intersectingであるとき， Polynomial techniqueを用いて証明する．

14.3.2 Sets with few intersection sizes 証明 （全ての取り得る共通部 分の大きさの集合）とする． つまり，任意の に対して， となる が存在．

14.3.2 Sets with few intersection sizes 証明続き 各集合 のincidence vector 明らかに に対して を定義する．

14.3.2 Sets with few intersection sizes 証明続き Lemma14.11より，各 は線形独立． 各 が存在するベクトル空間の次元を考 える．

14.3.2 Sets with few intersection sizes 証明続き の次数は高々 s {0, 1}nより， よって次数s以下の純単項式が基底となる． （純単項式は各変数が高々1回現れる式） その数は よって

14.3.2 Sets with few intersection sizes 本質的に同様の議論で，以下の定理の 成立が言える． Theorem 14.14 L:整数の集合，p:素数とする． が以下を満たす このとき， 少なくとも1つの に対して

14.3.3 Construction Ramsey graphs 定義 サイズtのクリーク t頂点の集合で任意の各頂点間に枝がある． サイズtの独立集合 t頂点の集合で各頂点間に枝がない． Ramseyグラフ あるグラフがサイズtのクリークも独立集合も持たないとき，tに関するRamseyグラフという．

14.3.3 Construction Ramsey graphs

14.3.3 Construction Ramsey graphs tが与えられたとき，tに関するRamsey グラフとなるようなグラフの頂点数n の最大値が知りたい． のRamseyグラフが構成 できることを，polynomial technique （から導かれた14.3と14.4）を用いて 証明している． 省略

14.3.4 Bollobas theorem – another proof を満たすとき， polynomial techniqueを用いて証明． 省略．

14.4 Combinatorics of linear spaces 代数的特徴を用いて様々な結果を述べ てきた． 今度はcombinatorialな特徴を用いて出 来る証明を紹介する．

14.4.1 Universal sets from linear codes 定義: (n, k)-universal (cf.11.3) が(n, k)-universalであるとは， 任意の部分集合 に対して，AのSへの射影 が の配 位を含む． 射影

14.4.1 Universal sets from linear codes (n, k)-universalの例 n=3，k=2のとき よってこのAは(3, 2)-universal

14.4.1 Universal sets from linear codes 定義: 最小距離(minimal distance) Cの異なる2要素間のハミング距離最小値． 線形符号Cの最小距離は，最小重み(ハ ミング重みの最小値)と一致する． ∵線形符号には零ベクトルが含まれる

14.4.1 Universal sets from linear codes Proposition 14.17 を長さnの線形符号とし， の最小距離をk+1とする． このとき， は(n, k)-universal 証明 とすると， は の線形部分空間．

14.4.1 Universal sets from linear codes 証明続き （Proposition14.2より） が真部分空間(proper subspace)である． ⇔任意のベクトル が非自明な線形 関係 を満たし，その台 (support) が に含まれる． の要素は全ての関係 その最小距離は， 以下． より，Cは(n, k)-universal．

14.4.2 Short linear combinations 0－1ベクトルの集合Aが与えられたと き，Aの高々k個のベクトルの和で spanAの全てのベクトルが表せるよう な最小のkについて知りたい． このkをspanning diameterという． を満たすαを用いてk をバウンドする定理を証明． 省略．

14.5 The flipping cards game 線形結合や内積がベクトルの有用な情 報を符号化するために使われることが 多い． あるゲームを例にこの手法を紹介する．

14.5 The flipping cards game 限られたビットへのアクセスで かどうか判定したい． 任意の瞬間に各 の内，高々1つし か見ることができない． この問題を次のようなゲームに対応さ せる．

14.5 The flipping cards game 表 : u １ ０ ０ １ １ 裏 : v 対応するビットの数字が両面に書かれ たn枚のカードがある． 全てのカードを見ることができるが， 片面しか見えない．

14.5 The flipping cards game １ ０ ０ １ １ カードから得られる 情報を書き込む 1回の探査（probe） 1枚以上のカードをめくる． カードから得られる情報を再利用不可の メモリに書き込む． 次の探査後には新しいメモリを使う．

14.5 The flipping cards game 今見えているカードとメモリの情報か ら，全てのカードの両面が一致してい るかどうかわかるまで探査を繰り返す． できるだけ少ないメモリで判定したい． nビットあれば十分なことは自明． をそのままメモリに書き込み，全ての カードをめくって を見れば判定できる．

14.5 The flipping cards game Theorem 14.21 のとき， 回の探査と ビットの書き込みで判定できる． 証明（プロトコルを示す） と を長さ の要素に分割する． 初めの探査で を見て を計算し，メモ リに書き込む．（ ビット使用） （ 上の演算）

14.5 The flipping cards game 証明続き 次の 回の探査を次のように行う． 回目の探査に， 番目の要素のカード（ 枚）をめくる． を計算する． 得られた が と一致するか調べる． 全てが と一致すれば ， そうでなければ と判定する．

14.5 The flipping cards game 証明続き このプロトコルの正しさを示す． と判定したとき，2回目の探査の後 より， となる． 以降同様の議論により， となる．

14.5 The flipping cards game Theorem14.22 回の探査と，1回の探査当たり ビットの書き込みで判定できる 証明（概略）