定理2.3.1 - lab2.kuis.kyoto-u.ac.jp.pptVIP

定理2.3.1 節点数nの完全グラフ　　があり、 その枝を全て二色（赤、青）で色分けする。 そのとき節点数aの単一色の完全グラフ　　が 　　　　　 個以下である塗りわけ方が存在する。 証明：定理2.3.1 全枝を確率1/2で赤、青に塗り分ける。 ある節点数aの節点集合　　 があり、 　　　　を、　　が単一色完全グラフであるとき１，そうでなければ０を表す確率変数とする。 期待値　　　　　は　　　　　となる。 証明：定理2.3.1 　　を節点数aの単一色な完全グラフ　　　の数とする。　　の期待値は以下で表される。 期待値が以上の値なので 　　　　とするような塗り分け方が存在する□ 定理2.3.2 節点数m,nの完全二部グラフ　　　　があり、 　その枝を全て二色（赤、青）で色分けする。 そのとき、節点数a,bの単一色な完全二部グ 　ラフ　　　が　　　　　　　　個以下であるような塗 り分け方が存在する。 ※頂点数mの集合は頂点数aの集合に対応し、 頂点数nの集合は頂点数bの集合に対応する 証明：定理2.3.2 全枝を確率1/2で赤、青に塗り分ける。 ある節点数a,bの節点集合　　　があり、 　　　　を、　　が単一色完全二部グラフであるとき１，そうでなければ０を表す確立変数とする。 期待値　　　　は　　　　となる。 証明：定理2.3.2 　　を節点数aの単一色な完全二部グラフ　　　の数とする。　　の期待値は以下で表される。 期待値が以上の値なので 　　　　とするのような塗り分け方が存在する□ 定理2.4.1 任意の　　　　　　　　　　　　　　　　　に対して、 　以下を満たす　　　　　　　　　　　　が存在する。 同様に以下を満たす　　　　　　　　　　 も存在する。 証明：定理2.4.1 　　　　　　　　に確率1/2で{-1,+1}を当てはめる。 　　　　　　　　　　　　　　　　　　　　　　　　　とおく。 展開すると 　　の期待値 証明：定理2.4.1 i≠jのとき 　　　∵　　は確率1/2で{-1,+1}をとる i=jのとき よって 証明：定理2.4.1 　　　　　　　より　　　　　　　　　　　とするような 　割り当て　　　　　　　　　が存在する。 　　　　　　　　　　　　　　　　より、 　平方根をとることで定理2.4.1を得られる□ 定理2.4.2 任意の　　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　に対して、 　以下を満たす　　　　　　　　　　　　が存在する。 　　　　　　　　　　　　　　　　　　　　　 　　　※ただし 証明：定理2.4.2 　それぞれに確率　　で１、　　　で０を割り当てる。 　　　　　　　　とおく 展開すると 期待値は　 証明：定理2.4.2 i≠jのとき 　　　　　　　　　　　　　　∵ i=jのとき 証明：定理2.4.2 以上より　　　　　　　　　　　　　　　とするような 割り当て　　　　　　　　　が存在し、　　の平方根をとることで定理2.4.2を得られる□　 *