✦ LIBER ✦

New lower bounds of some diagonal Ramsey numbers

✍ Scribed by Filip Guldan; Pavel Tomasta

Publisher: John Wiley and Sons
Year: 1983
Tongue: English
Weight: 122 KB
Volume: 7
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190070118

No coin nor oath required. For personal study only.

✦ Synopsis

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 results, e.g., upper or lower bounds.

Our aim in what follows is the construction of self-complementary graphs containing no K,, for appropriate n. Greenwood and Gleason 141 used the quadratic residues of a finite field to determine the exact values of the Ramsey numbers r(k,k) for k = 3 and 4. Abbott [ l ] has shown that r(5,5) > 37. It was proved by Lin and Burling independently that r(5,5) > 41 in 1972, though this result was not published. The same result has been proved by Hanson [5]. Kalbfleisch [6] established r(6,6) > 101. Further results for

📜 SIMILAR VOLUMES

Tidier Examples for Lower Bounds on Diag

Tidier Examples for Lower Bounds on Diagonal Ramsey Numbers

✍ Colin McDiarmid; Angelika Steger 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 266 KB

There is a family (H k ) of graphs such that H k has order (1+o(1))(-2Âe) k 2 kÂ2 but has no clique or stable set of order k. This result of Spencer provides the best known lower bound for the diagonal Ramsey numbers R(k, k). Here we see that the graphs H k can be taken to be regular, self-complemen

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 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

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

New Upper Bounds for Ramsey Numbers

✍ Y.R Huang; K.M Zhang 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 79 KB

The Ramsey number R(G 1 , G 2 ) is the smallest integer p such that for any graph Some new upper bound formulas are obtained for R(G 1 , G 2 ) and R(m, n), and we derive some new upper bounds for Ramsey numbers here.