EC14.3-14.5_kohta

14. The Basic Method
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

簡単に構成可能なRamseyグラフ
◦ t=5の例

できるだけnを大きくしたい．
14.3.3 Construction Ramsey graphs
tが与えられたとき，tに関するRamsey
グラフとなるようなグラフの頂点数n
の最大値が知りたい．

のRamseyグラフが構成
できることを，polynomial technique
（から導かれた14.3と14.4）を用いて
証明している．
 省略

14.3.4 Bollobas theorem – another proof

Theorem14.16
◦
◦
:サイズrの集合と
:サイズsの集合が
◦ を満たすとき，
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

定義: 線形符号(linear code)
◦ 長さnの(2進)線形符号
とは，
の線形部分空間となる2値ベクトルの
集合

定義: 最小距離(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

長さ n の2つの0-1ベクトル
限られたビットへのアクセスで
かどうか判定したい．
 任意の瞬間に各
の内，高々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回の探査当たり
ビットの書き込みで判定できる
証明（概略）

Download Report