Ramsey numbers and the size of graphs

Details Ramsey numbers and the size of graphs Ramsey numbers and the size of graphs

2007-06-27

arxiv.org/abs/0706.4102v1

Mathematics

Combinatorics

Scientific paper

For two graph H and G, the Ramsey number r(H, G) is the smallest positive integer n such that every red-blue edge coloring of the complete graph K_n on n vertices contains either a red copy of H or a blue copy of G. Motivated by questions of Erdos and Harary, in this note we study how the Ramsey number r(K_s, G) depends on the size of the graph G. For s \geq 3, we prove that for every G with m edges, r(K_s,G) \geq c (m/\log m)^{\frac{s+1}{s+3}} for some positive constant c depending only on s. This lower bound improves an earlier result of Erdos, Faudree, Rousseau, and Schelp, and is tight up to a polylogarithmic factor when s=3. We also study the maximum value of r(K_s,G) as a function of m.

Affiliated with

Also associated with

No associations

Rating

Ramsey numbers and the size of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ramsey numbers and the size of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ramsey numbers and the size of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455879