✦ LIBER ✦

New Lower Bounds for Ramsey Numbers of Graphs and Hypergraphs

✍ Scribed by Felix Lazebnik; Dhruv Mubayi

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 146 KB
Volume: 28
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.2001.0794

No coin nor oath required. For personal study only.

✦ Synopsis

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, Z. Füredi, and D. Mubayi (J. Combin. Theory Ser. B 79 (2000), 66-86), we prove that

where the lower bound holds when t and k are both powers of a prime p. When t = 1, we improve the lower bound by 1, proving that r k C 4 ≥ k 2 + 2 for any prime power k. This extends the result of F. Lazebnik and A. J. Woldar (J. Combin. Theory Ser. B 79 (2000), 172-176), which proves the same bound when k is an odd prime power. These results are generalized to hypergraphs in the following sense. Fix integers r s t ≥ 2. Let r s t be the complete r-partite r-graph with r -2 parts of size 1, one part of size s, and one part of size t (note that 2 s t = K s t ). We prove that tk 2 -k + 1 ≤ r k r 2 t + 1 ≤ tk 2 + k + r

📜 SIMILAR VOLUMES

New Upper and Lower Bounds for Ramsey Nu

New Upper and Lower Bounds for Ramsey Numbers

✍ Huang Yi Ru; Yang Jian Sheng 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 76 KB

Lower bounds for lower Ramsey numbers

✍ Ralph Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract For any graph __G__, let __i__(__G__) and μ;(__G__) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers __m__ and __n__, the lower Ramsey number __s__(__m, n__) is the largest integer __p__ so that every graph of or

New lower bounds of some diagonal Ramsey

New lower bounds of some diagonal Ramsey numbers

✍ Filip Guldan; Pavel Tomasta 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB 👁 1 views

A new construction of self-complementary graphs containing no Klo or K , is described. This construction gives the Ramsey number lower bounds r(10,lO) 2 458 and r(1 1,l 1 ) 2 542. The problem of determining the Ramsey numbers is known to be very difficult and so we are often satisfied with partial

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

Bounds for the ramsey number of a discon

Bounds for the ramsey number of a disconnected graph versus any graph

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB 👁 1 views

## Abstract Bounds are determined for the Ramsey number of the union of graphs versus a fixed graph __H__, based on the Ramsey number of the components versus __H__. For certain unions of graphs, the exact Ramsey number is determined. From these formulas, some new Ramsey numbers are indicated. In p

New bounds for the chromatic number of g

New bounds for the chromatic number of graphs

✍ Manouchehr Zaker 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph