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

نویسندگان
لیلا ماهرانی 1
غلامرضا امیدی 2
1 دانشگاه صنعتی اصفهان
2 دانشگاه صنعتی اصفهان و پژوهشکده ی دانش های بنیادین(IPM)
چکیده
چکیده

n ، کوچکترین عدد طبیعی G و H برای دو گراف دلخواه R(H;G) عدد رمزی

با دو رنگقرمز و n است به طوری که در هر ۲-رنگ آمیزی یالی گراف کامل از مرتب هی

از رنگ G از رنگقرمز یا زیرگراف یک ریخت با H آبی، بتوان زیرگراف یک ریخت با

نمایش می دهیم. در سال ۱۹۸۳ اردوش R(G) را به اختصار با R(G;G) آبی یافت.

یالی و بدون رأس m موجود است به طوری که برای هر گراف c > حدس زد که ثابت ۰

. این حدس در سال ۲۰۱۱ توسط سوداکو اثبات R(G)  ۲c

p

m ، داریم G تنهای

شد. ما در این مقاله نتیجه ی سوداکو را تعمیم می دهیم و سپس چند نتیجه ی جالب

به دست می آوریم.
کلیدواژه‌ها
عدد رمزی
عدد رمزی قطری
حدس اردوش

عنوان مقاله English

Around a conjecture of Erdos in graph Ramsey theory

نویسندگان English

Leila Maherani 1
Gholamreza Omidi 2
1 Isfahan University of technology
2 Isfahan University of technology and (IPM)
چکیده English

For given graphs G1 and G2 the Ramsey number R(G1;G2), is the smallest positive

integer n such that each blue-red edge coloring of the complete graph Kn contains a blue

copy of G1 or a red copy of G2. In 1983, Erd}os conjectured that there is an absolute constant

c such that R(G) = R(G;G)  2c

p

m 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 extention

of this result. As a corollary of our result we have R(G1;G2)  2250

p

m for graphs G1 and

G2 with no isolated vertices and m1 and m2 edges, respectively, where m = fm1;m2g

Keywords: Ramsey number, Erd}os' conjecrure.

کلیدواژه‌ها English

Ramsey number
Diagonal Rmsey number
Erdos' conjecrure
[1] N. Alon, M. Krivelevich and B. Sudakov, Turán numbers of bipartite graphs

and related Ramsey-type questions, Combin. Probab. Comput. 12 (2003),

477-494.



[2] D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of

Math. 170 (2009), 941-960.



[3] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc.

53 (1947), 292-294.



[4] P. Erdős, On some problems in graph theory, combinatorial analysis and

combinatorial number theory, Graph Theory and Combinatorics, Cambridge,

(1983), Academic Press, London, (1984), 1-17.



[5] P. Erdős and R. Graham, On partition theorems for finite graphs, in: Infinite

and Finite Sets, vol. I, Colloq., Keszthely, (1973), in: Colloq. Math.

Soc. Janos Bolyai, vol. 10, North-Holland, Amsterdam, (1975), 515-527.



[6] P. Erdős and G. Szekeres, A Combinatorial problem in geometry, Compos.

Math. 2 (1935), 463-470.



[7] J. Fox and B. Sudakov, Dependent Random Choice, Random Struct. Algorithms

38 (2011), 68-99.



[8] S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994),

Dynamic Surveys, DS1.12 (August 4, 2009).



[9] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc.2 30

(1930), 264-286.



[10] V. Rosta, Ramsey Theory Applications, Electron. J. Combin. (2004), 1-43.



[11] B. Sudakov, A Conjecture of Erdős on graph Ramsey numbers, Advances

In Math. 227 (2011), 601-609.