確率的方法

完全グラフがあると仮定します${\displaystyle n}$頂点。我々は、(十分に小さい値の場合) を示したい。${\displaystyle n}$グラフのエッジを2色（例えば赤と青）で着色することで、完全な部分グラフが存在しないことが可能である。${\displaystyle r}$頂点は単色である（すべての辺が同じ色で着色されている）。

そのためには、グラフをランダムに色付けします。各エッジを確率で独立に色付けします。${\displaystyle 1/2}$赤であることと${\displaystyle 1/2}$青色であること。単色部分グラフの期待数を計算します。${\displaystyle r}$頂点は以下のとおりです。

任意の集合に対して${\displaystyle S_{r}}$の${\displaystyle r}$グラフの頂点から変数を定義します${\displaystyle X(S_{r})}$である${\displaystyle 1}$すべてのエッジが${\displaystyle r}$頂点は同じ色で、${\displaystyle 0}$それ以外の場合は、単色数に注意してください。${\displaystyle r}$-サブグラフは、${\displaystyle X(S_{r})}$考えられるすべての部分集合について${\displaystyle S_{r}}$個々のセットごとに${\displaystyle S_{r}^{i}}$期待値​${\displaystyle X(S_{r}^{i})}$これは、すべての${\displaystyle C(r,2)}$エッジ${\displaystyle S_{r}^{i}}$同じ色です。

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

（${\displaystyle 2}$（これは、可能な色が2種類あるためです。）

これは、${\displaystyle C(n,r)}$選択できた可能性のある部分集合、つまり${\displaystyle i}$範囲は${\displaystyle 1}$に${\displaystyle C(n,r)}$。したがって、合計は次のようになります。${\displaystyle E[X(S_{r}^{i})]}$全体${\displaystyle S_{r}^{i}}$は

$\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

期待値の合計は合計の期待値です（変数が独立しているかどうかに関係なく）、したがって合計の期待値（すべての単色数の期待値）${\displaystyle r}$-サブグラフ)は

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

この値がより小さい場合どうなるかを考えてみましょう${\displaystyle 1}$単色光の数の期待値は${\displaystyle r}$-サブグラフは厳密に以下より小さい${\displaystyle 1}$単色数を満たす着色が存在する${\displaystyle r}$-サブグラフは厳密に以下より小さい${\displaystyle 1}$単色の数${\displaystyle r}$このランダム彩色における部分グラフの数は非負の整数であるため、${\displaystyle 0}$（${\displaystyle 0}$は、より小さい唯一の非負整数です。${\displaystyle 1}$)したがって、

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

（例えば、${\displaystyle n=5}$そして${\displaystyle r=4}$) 単色がない着色が存在する必要がある${\displaystyle r}$-部分グラフ。^{[ a ]}

ラムゼイ数の定義によれば、これは次のことを意味する。${\displaystyle R(r,r)}$より大きい必要がある${\displaystyle n}$。 特に、${\displaystyle R(r,r)}$少なくとも指数関数的に成長しなければならない${\displaystyle r}$。

この議論の弱点は、全く非建設的であることだ。このような彩色を見つける問題は、50年以上も未解決のままである。

エルデシュによる1959年の論文（下記参照）では、グラフ理論における次の問題が取り上げられています。正の整数gとkが与えられたとき、長さが少なくともgであるサイクルのみを含むグラフGが存在し、かつGの彩色数が少なくともkであるグラフGは存在するか？

任意のgとkに対してそのようなグラフが存在することが示され、その証明は比較的簡単です。nを非常に大きくして、 n 個の頂点を持つランダムグラフGを考えます。Gのすべての辺は確率p = n ^{1/ g −1}で存在します。正の確率で、 G が次の 2 つの性質を満たすことを示します。

性質1. Gは、長さがgより小さいサイクルを最大n /2個含む。

証明。長さがgより小さいサイクルの数をXとする。n個の頂点を持つ完全グラフにおける長さiのサイクルの数は

$\displaystyle {\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}}$

そして、それぞれが確率p ⁱでGに存在する。したがって、マルコフの不等式により、

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

したがって、 nが十分に大きい場合、性質1は1/2以上の確率で成立する。

性質2. Gにはサイズが の独立集合は含まれない${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$。

証明。YをGにおける最大の独立集合のサイズとする。明らかに、

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

いつ

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}$したがって、nが十分に大きい場合、性質2は1/2以上の確率で成り立つ。

nが十分に大きい場合、分布から得られるグラフが両方の特性を持つ確率は正になります。なぜなら、これらの特性に関する事象は互いに排他的ではないからです（もし排他的であれば、それらの確率の合計は1より大きくなります）。

ここでのトリックは、G がこれらの 2 つの性質を持っているため、 Gから最大でn /2個の頂点を削除して新しいグラフG′を取得できるということです。${\displaystyle n'\geq n/2}$長さが少なくともgのサイクルのみを含む頂点。この新しいグラフには、サイズの独立した集合がないことがわかります。${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$G′は少なくともk個の独立した集合に分割されなければならず、したがって、少なくともk個の彩色数を持つ。

この結果は、グラフの彩色数を計算することがなぜこれほど難しいのかを示唆している。グラフが多くの色を必要とする局所的な理由（例えば、小さなサイクルなど）がない場合でも、彩色数は任意に大きくなる可能性がある。