r(Km,n)的一个构造型下界

A Note on a Lower Bound for r(Km,n)

摘要:

图G的Ramsey数r(G)是指最小的自然数N，满足当n>= N，对完全图K_n的边进行红蓝二着色时总包含单色的图G。 对于完全二部图Km,n，本文给出了当n充分大时，r(Km,n)>= 2^m(n- n^{0.525})的一个代数构造的证明。

关键词:Ramsey数;Paley图

Abstract:

Let G be a graph. The Ramsey number r(G) is the minimum integer N such that any two edge-coloring of K_N contains a monochromatic G. Using an algebraic construction it is shown that r(Km,n)>= 2^m(n- n^{0.525}) for large n.

Key words:Ramsey Number; Paley Graph