๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Tidier Examples for Lower Bounds on Diagonal Ramsey Numbers

โœ Scribed by Colin McDiarmid; Angelika Steger

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
266 KB
Volume
74
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

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-complementary, and pseudo-random.

๐Ÿ“œ SIMILAR VOLUMES

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

Lower bounds for lower Ramsey numbers
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 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,

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