Ramsey numbers and the size of graphs
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-06-27 | |
| dc.date.accessioned | 2026-07-07T08:12:50Z | |
| dc.date.available | 2026-07-07T08:12:50Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0706.4102 | |
| dc.identifier | http://arxiv.org/abs/0706.4102 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132590 | |
| dc.subject | Combinatorics | |
| dc.title | Ramsey numbers and the size of graphs | |
| dc.type | text |