✦ LIBER ✦

A new upper bound for the bipartite Ramsey problem

✍ Scribed by David Conlon

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 89 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20317

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider the following question: how large does n have to be to guarantee that in any two‐coloring of the edges of the complete graph K~n,n~ there is a monochromatic K~k,k~? In the late 1970s, Irving showed that it was sufficient, for k large, that n ≥ 2^k − 1^ (k − 1) − 1. Here we improve upon this bound, showing that it is sufficient to take

📜 SIMILAR VOLUMES

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.

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

On the Ramsey Problem for Multicolor Bip

On the Ramsey Problem for Multicolor Bipartite Graphs

✍ W.A Carnielli; E.L Monte Carmelo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 85 KB

Given i, j positive integers, let K denote a bipartite complete graph and let i, j ## Ž . R m, n be the smallest integer a such that for any r-coloring of the edges of K r a, a one can always find a monochromatic subgraph isomorphic to K . In other m, n Ž . Ä 4 words, if a G R m, n then every mat

An upper bound for the ramsey number r(K

An upper bound for the ramsey number r(K5 − e)

✍ H. Harborth; I. Mengersen 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

Upper and lower bounds for a pattern bom

Upper and lower bounds for a pattern bombing problem

✍ Alan R. Washburn 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 403 KB 👁 1 views

A new upper bound for the harmonious chr

A new upper bound for the harmonious chromatic number

✍ Edwards, Keith 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB 👁 2 views

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general