𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a Quasi-Ramsey problem

✍ Scribed by Paul Erdös; János Pach

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
368 KB
Volume
7
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved th2t if a graph G has at least cn log n vertices, then either G or its complement G contains a subgraph H with a t least n vertices and minimum degree a t least 1 V ( H ) I /2. This result is not far from being best possible, as is shown by a rather unusual random construction. Some related questions are also discussed.

📜 SIMILAR VOLUMES

On a Ramsey-type problem
On a Ramsey-type problem
✍ F. R. K. Chung 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 212 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

A Ramsey-type problem and the Turán numb
A Ramsey-type problem and the Turán numbers
✍ N. Alon; P. Erdős; D. S. Gunderson; M. Molloy 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract For each __n__ and __k__, we examine bounds on the largest number __m__ so that for any __k__‐coloring of the edges of __K~n~__ there exists a copy of __K~m~__ whose edges receive at most __k−__1 colors. We show that for $k \ge \sqrt{n}\;+\,\Omega(n^{1/3})$, the largest value of __m__ i

A new upper bound for the bipartite Rams
A new upper bound for the bipartite Ramsey problem
✍ David Conlon 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB 👁 1 views

## 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^_