Ramsey Numbers and the Size of Graphs

DOI10.1137/060667360MaRDI QIDQ3544246zbMATH OpenOpenAlexFDO

Authors Benny Sudakov

Publication date 5 December 2008

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

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

zbMATH Keywords

Ramsey numbersprobabilistic methods

Mathematics Subject Classification ID

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

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.

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}\)

Cited in

(24)

• Ramsey unsaturated and saturated graphs
• Two variants of the size Ramsey number
• The size‐Ramsey number of cubic graphs
• The Ramsey number of dense graphs
• Ramsey numbers, graph eigenvalues, and a conjecture of Cao and Yuan
• Lower bounds of size Ramsey number for graphs with small independence number
• Ramsey's theorem and self-complementary graphs
• 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
• A Ramsey problem of Harary on graphs with prescribed size
• scientific article; zbMATH DE number 811560 (Why is no real title available?)
• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• Three early problems on size Ramsey numbers
• A conjecture of Erdős on graph Ramsey numbers
• Size Ramsey number of bounded degree graphs for games
• Bounds on Ramsey games via alterations
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Ramsey numbers involving graphs with large degrees
• Ramsey Size Linear Graphs
• Graphs with arbitrary Ramsey number and connectivity
• scientific article; zbMATH DE number 1047725 (Why is no real title available?)

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)