ラムゼーの数の建設的な下限
ラムゼーの定理は次のように述べています
与えられた $s, t\in \mathbb{N}$、 有る $n\in \mathbb{N}$ すべてのグラフに対して $n$ 頂点、それは含まれています $s$-クリークまたはその補集合には、 $t$-クリーク。
一番小さい $n$ ステートメントを満たすことは、 $R(s, t)$。
記事「組み合わせ論における確率的手法、ニランジャン・バラチャンドランによる講義」で、次のステートメントを見つけました。
Nagyによって発見されたR（s、s）の建設的な下限は次のとおりです。 $$R(s, s)\ge \binom{s}{3}$$ （明示的に、彼の構造は次のようになります：任意のセットを取る $S$、そしてすべてのコレクションを回します $3$-の要素サブセット $S$ サブセットの交点が奇数の場合は、サブセットを接続してグラフに変換します。）
このグラフとその補集合に含まれていないことを証明できませんでした $s$-クリーク。この件での助けをいただければ幸いです。
回答
取りましょう $S = \{1, 2, \dots, s\}$。実際に示すことができるのは、Nagyのグラフが
- せいぜいサイズのクリーク $\max\{7, \frac{s-1}{2}\}$、および
- 最大で独立したサイズのセット $s-1$ 以下の場合 $s \not\equiv 0 \pmod 4$、そしてせいぜい $s$ いつ $s \equiv 0 \pmod 4$。
これはそれを示していません $R(s,s) \ge \binom s3$ すべてのために $s$、しかしそれはそれを示しています $R(s,s) > \binom s3$、そしてそれでも $R(\frac{s}{2}, s) > \binom s3$、無限に多くの値の場合 $s$。
まず、最大のクリークを見つけましょう。2つのケースがあります：
- クリークには $4$ の同じ要素で交差する頂点 $S$： いう、 $\{1,2,3\}$、 $\{1,4,5\}$、 $\{1,6,7\}$、および $\{1,8,9\}$。次に、他のすべての頂点に含まれている必要があります$1$：それ以外の場合は、それぞれの要素が必要になります $\{2,3\}$、 $\{4,5\}$、 $\{6,7\}$、および $\{8,9\}$、それは不可能です。そのようなクリークはせいぜい持つことができます$\frac{s-1}{2}$ 頂点。
- クリークには多くても含まれています $3$ の同じ要素で交差する頂点 $S$。いう$\{1,2,3\}$は頂点の1つです。その後、せいぜいあることができます$2$ それぞれを含む他の頂点 $1$、 $2$、または $3$、だからクリークはせいぜい $7$ 頂点。
次に、最大の独立集合を見つけましょう。ここで、独立集合の2つの頂点が共有する場合は注意してください$2$ 要素、および独立集合共有の3番目の頂点 $2$ それらの1つを持つ要素、それは少なくとも1つの要素を共有する必要があります（したがって $2$要素）他と。したがって、独立集合はクラスターで構成されている必要があり、クラスター内の任意の2つの頂点が共有されます$2$ 要素、およびクラスター外の任意の2つの頂点が共有します $0$。
繰り返しになりますが、クラスターは2つの異なる形状を持つことができます。
- クラスターが持っていると仮定します $3$ すべて同じを共有する頂点 $2$ 要素：言う、 $\{1,2,3\}$、 $\{1,2,4\}$、そして $\{1,2,5\}$。1つだけを含むクラスター内の別の頂点$\{1,2\}$ それぞれを含める必要があります $3$、 $4$、および $5$、それは不可能です。したがって、クラスターは$k$ フォームの頂点 $\{1,2,x\}$、「使い切る」 $k+2$ の要素 $S$。
- クラスターに最大で $2$ 任意を共有する頂点 $2$要素。その後、$\{1,2,3\}$ はクラスター内の頂点であり、クラスター内の他の各頂点には、 $\{1,2,3\}$、しかし、各種類の最大で1つが存在する可能性があります。 $4$頂点の合計。これらは少なくとも使い切る必要があります$4$ の要素 $S$、など $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$。
クラスターが使い切っていることがわかります $k$ の要素 $S$ せいぜい含むことができます $k$ 頂点、つまりクラスター全体に含めることができるのは最大で $S$頂点。ただし、これは、すべてのクラスターが2番目のタイプであり、のすべての要素をカバーしている場合にのみ可能です。$S$、必要です $s \equiv 0 \pmod 4$。