Around a conjecture of Erdos in graph Ramsey theory

Authors
1 Isfahan University of technology
2 Isfahan University of technology and (IPM)
Abstract
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.
Keywords

[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.