Ramsey Numbers and the Size of Graphs

DOI10.1137/060667360zbMATH Open1151.05037arXiv0706.4102OpenAlexW1965954841MaRDI QIDQ3544246FDOQ3544246

Authors: Benny Sudakov 

Publication date: 5 December 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0706.4102

Recommendations

• An upper bound on the ramsey number R(K₃, G) depending only on the size of the graph G
• scientific article; zbMATH DE number 426333
• Lower Ramsey numbers for graphs
• A Ramsey problem of Harary on graphs with prescribed size
• Ramsey numbers of several \(K_{t,s}\) and a large \(K_{m,n}\)

zbMATH Keywords

Ramsey numbersprobabilistic methods

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Connectivity (05C40) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cited In (24)

• The size‐Ramsey number of cubic graphs
• The Ramsey number of dense graphs
• Ramsey numbers, graph eigenvalues, and a conjecture of Cao and Yuan
• Ramsey's theorem and self-complementary graphs
• Lower bounds of size Ramsey number for graphs with small independence number
• The shift graph and the Ramsey degree of \([\mathbb N]^\omega\)
• Size Ramsey number of bipartite graphs and bipartite Ramanujan graphs
• Changing views of Ramsey numbers
• Ramsey numbers involving large dense graphs and bipartite Turán numbers
• Size Ramsey numbers for some regular graphs
• Title not available (Why is that?)
• A Ramsey problem of Harary on graphs with prescribed size
• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• Three early problems on size Ramsey numbers
• Bounds on Ramsey games via alterations
• Size Ramsey number of bounded degree graphs for games
• The Size Ramsey Number of Graphs with Bounded Treewidth
• A conjecture of Erdős on graph Ramsey numbers
• Ramsey Size Linear Graphs
• Ramsey numbers involving graphs with large degrees
• Graphs with arbitrary Ramsey number and connectivity
• Title not available (Why is that?)
• Ramsey unsaturated and saturated graphs
• Two variants of the size Ramsey number

This page was built for publication: Ramsey Numbers and the Size of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3544246)