グラフ理論

ランダムスパンサブグラフの色数



Chromatic Number Random Spanning Subgraph



解決：

$ k = 5 $（またはその他の固定$ k $）の場合、$ c $を好きなように選択できるため、頂点の数に関係なく、確率にある程度の制限が必要です。

実際、次の補題を証明すると、確率は最大で$ frac12 $であることを示すことができます。



$ H_1 $と$ H_2 $を同じ頂点セット上のグラフとし、$ H_1 cup H_2 $を$ H_1 $または$ H_2 $のいずれかに存在するすべてのエッジを取得して得られたグラフとします。次に、$ chi（H_1 cup H_2） le chi（H_1） cdot chi（H_2）$。

証拠： $ i in {1,2 } $に対して$ H_i $の$ r_i $ -coloring $ f_i $が与えられた場合、$ v $を与えることにより、$ H_1 cup H_2 $の$ r_1r_2 $ -coloringを構築できます。色$（f_1（v）、f_2（v））$。 $ v $と$ w $が$ H_1 cup H_2 $で隣接している場合、それらは$ H_1 $（および$ f_1（v） ne f_1（w）$）で隣接しているか、$ H_2で隣接しています。 $（および$ f_2（v） ne f_2（w）$）なので、どちらの場合も$（f_1（v）、f_2（v）） ne（f_1（w）、f_2（w））$になります。



$ G $のスパンサブグラフ$ G '$が与えられた場合、$ G' '$を$ G' $にない$ G $のすべてのエッジを取ることによって形成されたグラフとすると、$ 4 2 $または$ chi（G ''）> 2 $。したがって、すべての可能なグラフをペアに分割しました。少なくとも1つのグラフの色数が$ 2 $を超えています。つまり、$ Pr [ chi（G '） le 2] $は最大で$ frac12 $です。

これを使用して必要な一般的な境界を取得するには、エッジセット$ E $を$ Omega（k ^ 2）$の互いに素な部分$ E_1、E_2、 dots、E_t $に分割して、$ chi（ G_ {E_i}）すべての$ i $に対して ge 5 $。次に、ランダムに選択された$ E ' subseteq E $の場合、すべての$ iに対して$ chi（G_ {E' cap E_i}） le 2 $の場合にのみ、$ chi（G_ {E '}） le 2 $ $。これらは$ t $の独立したイベントであり、上記の引数では最大で$ frac12 $であるため、$ Pr [ chi（G_ {E '}） le 2] le 2 ^ {-t} $です。

$ E_1、 dots、E_t $を見つけるには、$ G $の$ k $色の$ f $を修正し、セット$ V_ {abcde} = f ^ {-1}（ {a、b、c、 d、e }）$一部の色$ a、b、c、d、e $。 $ E_ {abcde} $を$ V_ {abcde} $の頂点のペア間のすべてのエッジのセットとすると、$ chi（G_ {E_ {abcde}}）= 5 $であることを理解するのは難しくありません。 $ {a、b、c、d、e } $と$ {a '、b'、c '、d'、e '} $。



したがって、サイズ$ 5 $の$ {1,2、 dots、k } $の$ Omega（k ^ 2）$サブセットを選択する必要があります。そのうち、2つは複数の要素を共有しません。これは、確率的に使用して実行できます。一瞬の計算。