مطالعه حدسی از اردوش روی اعداد رمزی گراف ها

عدد رمزی r(h,g) به ازای گراف‌های داده شده‌ی h و g، کوچکترین عدد طبیعی n تعریف می‌شود به‌طوری‌که در هر 2-رنگ‌آمیزی یالی گراف کامل از مرتبه‌ی n با دو رنگ قرمز و آبی، بتوان زیرگراف تک‌رنگ یک‌ریخت با h از رنگ قرمز یا زیرگراف تک‌رنگ یک‌ریخت با g از رنگ آبی یافت. در سال 1983 اردوش حدس زد که ثابت c>0 موجود است به‌طوری‌که برای هر گراف m یالی و بدون راس تنهای g، داریم r(g,g)≤2^(c√m). این حدس در سال 2011 توسط سوداکو اثبات شد. ما در این مقاله با قرار دادن شرایط مناسب، نتیجۀ سوداکو را به گراف‌های g1 و g2 تعمیم می‌دهیم. هم‌چنین با قرار دادن g1=kn و g2=kl+h که در آن h یک گراف تنک است، نتیجه‌ی مشابهی برای r(g1,g2) به دست می‌آوریم.

around a conjecture of erdos in graph ramsey theory

for given graphs g1 and g2 the ramsey number r(g1;g2), is the smallest positiveinteger n such that each blue-red edge coloring of the complete graph kn contains a bluecopy of g1 or a red copy of g2. in 1983, erd}os conjectured that there is an absolute constantc such that r(g) = r(g;g) 2cpm for any graph g with m edges and no isolated vertices.recently this conjecture was proved by sudakov. in this short note, we give an extentionof this result. as a corollary of our result we have r(g1;g2) 2250pm for graphs g1 andg2 with no isolated vertices and m1 and m2 edges, respectively, where m = fm1;m2gkeywords: ramsey number, erd}os’ conjecrure.