Book contents
- Frontmatter
- Contents
- Preface
- 1 Ramsey classes: examples and constructions
- 2 Recent developments in graph Ramsey theory
- 3 Controllability and matchings in random bipartite graphs
- 4 Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5 Randomly generated groups
- 6 Curves over finite fields and linear recurring sequences
- 7 New tools and results in graph minor structure theory
- 8 Well quasi-order in combinatorics: embeddings and homomorphisms
- 9 Constructions of block codes from algebraic curves over finite fields
- References
2 - Recent developments in graph Ramsey theory
Published online by Cambridge University Press: 05 July 2015
- Frontmatter
- Contents
- Preface
- 1 Ramsey classes: examples and constructions
- 2 Recent developments in graph Ramsey theory
- 3 Controllability and matchings in random bipartite graphs
- 4 Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5 Randomly generated groups
- 6 Curves over finite fields and linear recurring sequences
- 7 New tools and results in graph minor structure theory
- 8 Well quasi-order in combinatorics: embeddings and homomorphisms
- 9 Constructions of block codes from algebraic curves over finite fields
- References
Summary
Abstract
Given a graph H, the Ramsey number r(H) is the smallest natural number N such that any two-colouring of the edges of KN contains a monochromatic copy of H. The existence of these numbers has been known since 1930 but their quantitative behaviour is still not well understood. Even so, there has been a great deal of recent progress on the study of Ramsey numbers and their variants, spurred on by the many advances across extremal combinatorics. In this survey, we will describe some of this progress.
1 Introduction
In its broadest sense, the term Ramsey theory refers to any mathematical statement which says that a structure of a given kind is guaranteed to contain a large well-organised substructure. There are examples of such statements in many areas, including geometry, number theory, logic and analysis. For example, a key ingredient in the proof of the Bolzano–Weierstrass theorem in real analysis is a lemma showing that any infinite sequence must contain an infinite monotone subsequence.
A classic example from number theory, proved by van der Waerden [212] in 1927, says that if the natural numbers are coloured in any fixed number of colours then one of the colour classes contains arbitrarily long arithmetic progressions. This result has many generalisations. The most famous, due to Szemerédi [206], says that any subset of the natural numbers of positive upper density contains arbitrarily long arithmetic progressions. This result has many generalisations. The most famous, due to Szemerédi [206], says that any subset of the natural numbers of positive upper density contains arbitrarily long arithmetic progressions.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2015 , pp. 49 - 118Publisher: Cambridge University PressPrint publication year: 2015
References
- 48
- Cited by