Ramsey Theory

Unsolved Problems and Results

Xiaodong Xu, Meilian Liang, Haipeng Luo, University of Science & Technology

• Publisher: De Gruyter
• Year: 2018
• ISBN:
  9783110576634
• Edition: 1
• Topic: Mathematics
• Subtopic: Algebra
• Index: Mathematics

Key problems and conjectures have played an important role in promoting the development of Ramsey theory, a field where great progress has been made during the past two decades, with some old problems solved and many new problems proposed. The present book will be helpful to readers who wish to learn about interesting problems in Ramsey theory, to see how they are interconnected, and then to study them in depth. This book is the first problem book of such scope in Ramsey theory. Many unsolved problems, conjectures and related partial results in Ramsey theory are presented, in areas such as extremal graph theory, additive number theory, discrete geometry, functional analysis, algorithm design, and in other areas. Most presented problems are easy to understand, but they may be difficult to solve. They can be appreciated on many levels and by a wide readership, ranging from undergraduate students majoring in mathematics to research mathematicians. This collection is an essential reference for mathematicians working in combinatorics and number theory, as well as for computer scientists studying algorithms.

Contents
Some definitions and notations
Ramsey theory
Bi-color diagonal classical Ramsey numbers
Paley graphs and lower bounds for R(k, k)
Bi-color off-diagonal classical Ramsey numbers
Multicolor classical Ramsey numbers
Generalized Ramsey numbers
Folkman numbers
The Erd?s–Hajnal conjecture
Other Ramsey-type problems in graph theory
On van der Waerden numbers and Szemeredi's theorem
More problems of Ramsey type in additive number theory
Sidon–Ramsey numbers
Games in Ramsey theory
Local Ramsey theory
Set-coloring Ramsey theory

Other problems and conjectures

1Some definitions and notations

In such a book of about 200 pages, many different topics in Ramsey theory or that are related to Ramsey theory will be discussed. We will use a large amount of terminology and notations. Hence, it is impossible for it to be self-contained.

In this chapter, we list some basic definitions in graph theory and graph Ramsey theory. More often than not, in this chapter, we will define only such terminology and notations that will be frequently used in this book. We will not cite the definitions of Folkman numbers, van der Waerden numbers, etc. here; instead they will be defined in the subsequent chapters devoted to them.

Throughout this book, let a, b, s, t, k, l, m, n, r and ki be positive integers. In many similar cases, we suppose that the numbers we use are positive integers, unless otherwise specified. The cardinality of a finite set A is denoted by |A|. Let [n] = {1, . . . , n} denote the set consisting of the first n positive integers. The set of all positive integers is denoted by ℕ, and the set of all integers is denoted by ℤ.

1.1Some definitions in graph theory

We will only write a small introduction to the terminology in graph theory that will be used in the book. Fortunately, much of the standard graph theoretic terminology is so intuitive that it is easy to understand. Some definitions in graph theory that cannot been found in this section, for instance, the Hamiltonian graph, may be found in the textbook [45] by Bondy and Murty, or the textbook [78] by Reinhard Diestel. Note that the textbook of Bondy and Murty that we suggest here is the 1976 version, not the advanced course of many more pages that was published in 2007.

We believe that for graph theory, unlike for most of other branches of mathematics, an advanced course that includes many topics may not be necessary for most readers because they will be only interested in a few topic, and an advanced course would be used only as a handbook. However, as a handbook, some parts of these advanced courses on graph theory may soon be outdated. An advanced course on a few related topics in graph theory may be more useful.

Suppose G is a graph. The set of its vertices is denoted by V(G), and the set of its edges by E(G). |V(G)| and |E(G)| are called the order and size of graph G, respectively. Sometimes we denote the order of graph G by n(G) or |V(G)|. For a finite graph G, both |V(G)| and |E(G)| are finite. All graphs considered in this book are finite graphs, unless otherwise specified.

For graph G, the complement of G denoted by G is the graph with t...

Table of contents

• Cover
• Title Page
• Copyright
• Preface
• Contents
• 1 Some definitions and notations
• 2 Ramsey theory
• 3 Bi-color diagonal classical Ramsey numbers
• 4 Paley graphs and lower bounds for R(k, k)
• 5 Bi-color off-diagonal classical Ramsey numbers
• 6 Multicolor classical Ramsey numbers
• 7 Generalized Ramsey numbers
• 8 Folkman numbers
• 9 The Erdős–Hajnal conjecture
• 10 Other Ramsey-type problems in graph theory
• 11 On van der Waerden numbers and Szemerédi’s theorem
• 12 More problems of Ramsey type in additive number theory
• 13 Sidon–Ramsey numbers
• 14 Games in Ramsey theory
• 15 Local Ramsey theory
• 16 Set-coloring Ramsey theory
• 17 Other problems and conjectures
• Epilogue
• Bibliography
• Index