𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Shift graphs and lower bounds on Ramsey numbers rk(l; r)

✍ Scribed by Dwight Duffus; Hannon Lefmann; Vojtěch Rödl

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
380 KB
Volume
137
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this note we will obtain some lower bounds for the Ramsey numbers rk(l;r), where rk(l;r ) is the least positive integer n such that for every coloring of the k-element subsets of an n-element set with r colors there always exists an/-element set, all of whose k-element subsets are colored the same. In particular, improving earlier results of Hirschfeld and complementing results of Erd6s, Hajnal and Rado, we will show for r>~ 3 that rk(l;r), l>~k+ l, grows like a tower, while determining the growth of rk(k+ 1;2) remains a problem.

📜 SIMILAR VOLUMES

New Lower Bounds on the Multicolor Ramse
New Lower Bounds on the Multicolor Ramsey Numbers rk(C4)
✍ Felix Lazebnik; Andrew J. Woldar 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 85 KB

The multicolor Ramsey number r k (C 4 ) is the smallest integer n for which any k-coloring of the edges of the complete graph K n must produce a monochromatic 4-cycle. It was proved earlier that r k (C 4 ) k 2 &k+2 for k&1 being a prime power. In this note we establish r k (C 4 ) k 2 +2 for k being

New Lower Bounds for Ramsey Numbers of G
New Lower Bounds for Ramsey Numbers of Graphs and Hypergraphs
✍ Felix Lazebnik; Dhruv Mubayi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 146 KB 👁 1 views

## dedicated to the memory of rodica simion Let G be an r-uniform hypergraph. The multicolor Ramsey number r k G is the minimum n such that every k-coloring of the edges of the complete r-uniform hypergraph K r n yields a monochromatic copy of G. Improving slightly upon results from M. Axenovich,

A class of self-complementary graphs and
A class of self-complementary graphs and lower bounds of some ramsey numbers
✍ C. R. J. Clapham 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 1 views

## Abstract A method is described of constructing a class of self‐complementary graphs, that includes a self‐complementary graph, containing no __K__~5~, with 41 vertices and a self‐complementary graph, containing no __K__~7~, with 113 vertices. The latter construction gives the improved Ramsey num

A constructive approach for the lower bo
A constructive approach for the lower bounds on the Ramsey numbers R (s, t)
✍ Xu Xiaodong; Xie Zheng; Stanisław P. Radziszowski 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB 👁 1 views

## Abstract Graph __G__ is a (__k__, __p__)‐graph if __G__ does not contain a complete graph on __k__ vertices __K__~__k__~, nor an independent set of order __p__. Given a (__k__, __p__)‐graph __G__ and a (__k__, __q__)‐graph __H__, such that __G__ and __H__ contain an induced subgraph isomorphic t

On graphs with linear Ramsey numbers
On graphs with linear Ramsey numbers
✍ R. L. Graham; V. Rödl; A. Ruciński 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 1 views