nach oben

2022 | Buch

Kapitel lesen Erstes Kapitel lesen

Elementary Methods of Graph Ramsey Theory

verfasst von: Yusheng Li, Qizhong Lin

Verlag: Springer International Publishing

Buchreihe : Applied Mathematical Sciences

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is intended to provide graduate students and researchers in graph theory with an overview of the elementary methods of graph Ramsey theory. It is especially targeted towards graduate students in extremal graph theory, graph Ramsey theory, and related fields, as the included contents allow the text to be used in seminars.

It is structured in thirteen chapters which are application-focused and largely independent, enabling readers to target specific topics and information to focus their study. The first chapter includes a true beginner’s overview of elementary examples in graph Ramsey theory mainly using combinatorial methods. The following chapters progress through topics including the probabilistic methods, algebraic construction, regularity method, but that's not all.

Many related interesting topics are also included in this book, such as the disproof for a conjecture of Borsuk on geometry, intersecting hypergraphs, Turán numbers and communication channels, etc.

Inhaltsverzeichnis

Frontmatter

1. Existence

Abstract

A typical result in Ramsey theory states that if a mathematical object is partitioned into finitely many parts, then one of the parts must contain a sub-object of particular property. The smallest size of the large object such that the sub-object exists is called Ramsey number.

Yusheng Li, Qizhong Lin

2. Small Ramsey Numbers

Abstract

What are exact values of 𝑟 (𝑚, 𝑛)? This is more challenging than to show their existence. Let us call the classical Ramsey number 𝑟 (𝑚, 𝑛) to be the small Ramsey number if 𝑚 and 𝑛 are small. In this chapter, we shall obtain some exact values of small Ramsey numbers in the first section.

Yusheng Li, Qizhong Lin

3. Basic Probabilistic Method

Abstract

The probabilistic method is a powerful tool for tackling problems in many areas of mathematics, such as number theory, algebra, analysis, geometry, combinatorics, and computer science, etc.

Yusheng Li, Qizhong Lin

4. Random Graph

Abstract

The study of random graphs should go back to Erdős and Rényi (1947, 1959, 1960, 1961), in which they discovered that the random graphs were often useful in tackling extremal problems in graph theory.

Yusheng Li, Qizhong Lin

5. Lovász Local Lemma

Abstract

When applying the probabilistic method, some typical ways are computing expectation, estimating tails of probability and applying Lovász Local Lemma (Lovász, born on 1948, recipient of the 1999 Wolf prize and the 2021 Abel prize), etc.

Yusheng Li, Qizhong Lin

6. Constructive Lower Bounds

Abstract

To compare the lower bounds obtained from probabilistic method previously, we will take a look at the lower bounds of the classic Ramsey numbers from the constructive method. In this chapter, we shall introduce a disproof of a conjecture of Borsuk in geometry and related properties of intersecting hypergraphs.

Yusheng Li, Qizhong Lin

7. Turán Number and Related Ramsey Number

Abstract

Paul Turán (August 18, 1910–September 26, 1976) was a Hungarian mathematician who worked primarily in number theory. As his long collaborator, Paul Erdős wrote of Turán, “In 1940–1941 he created the area of extremal problems in graph theory which is now one of the fastest-growing subjects in combinatorics.”.

Yusheng Li, Qizhong Lin

8. Communication Channels

Abstract

Ramsey theory has been applied to information theory in various ways. In this chapter, we shall see that the connection between Ramsey theory and communication channel is natural.

Yusheng Li, Qizhong Lin

9. Dependent Random Choice

Abstract

The method of dependent random choice has many applications, particularly for extremal problems that deal with embedding a small or sparse graph into a dense graph, in which the most of embedded graphs are bipartite.

Yusheng Li, Qizhong Lin

10. Quasi-Random Graphs

Abstract

Random graphs have been proven to be one of the most important tools in modern graph theory.

Yusheng Li, Qizhong Lin

11. Regularity Lemma and van der Waerden Number

Abstract

Bartel L. van der Waerden (February 2, 1903–January 12, 1996) was a Dutch mathematician, who published his Algebra, an influential two-volume treatise on abstract algebra at age 27.

Yusheng Li, Qizhong Lin

12. More Ramsey Linear Functions

Abstract

From an application of the regularity lemma by Chvátal, Rödl, Szemerédi and Trotter (1983) introduced in the last chapter,we knowthat the family of graphs with bounded maximum degree is Ramsey linear.

Yusheng Li, Qizhong Lin

13. Various Ramsey Problems

Abstract

Ramsey theorem has inspired many striking and difficult problems with a lot of variations. We discuss some of them in this chapter, particularly size Ramsey numbers, bipartite Ramsey numbers, and Folkman numbers, etc.

Yusheng Li, Qizhong Lin

Backmatter

Titel: Elementary Methods of Graph Ramsey Theory
verfasst von: Yusheng Li
Qizhong Lin
Verlag: Springer International Publishing
Electronic ISBN: 978-3-031-12762-5
Print ISBN: 978-3-031-12761-8
DOI: https://doi.org/10.1007/978-3-031-12762-5