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
Author(s): Yusheng Li, Qizhong Lin
Series: Applied Mathematical Sciences, 211
Publisher: Springer
Year: 2022
Language: English
Pages: 347
City: Cham
Tags: Graph Theory, Ramsey Numbers
Preface
Contents
Existence
Terminology
General Upper Bounds
Upper Bounds for rk(3)
Some Early Ramsey Numbers
Hypergraph Ramsey Number
Exercises
Small Ramsey Numbers
Ramsey Folklore
Finite Field and r3(3)
Schur Numbers
Paley Graphs
Combination of Paley Graphs
Spectrum and Independence Number
Exercises
Basic Probabilistic Method
Some Basic Inequalities
A Lower Bound of r(n,n)
Pick Vertices Semi-Randomly
Independence Number of Sparse Graphs
Upper Bounds for r(m,n)
Odd Cycle versus Large Kn
The First Two Moments
Chernoff Bounds
Exercises
Random Graph
Preliminary
Lower Bounds for r(m,n)
More Applications of Chernoff Bounds
Properties of Random Graphs
Some Behaviors of Almost All Graphs
Parameters of Random Graphs
Threshold Functions
Poisson Limit
Exercises
Lovász Local Lemma
Lovász Local Lemma
Improved Lower Bounds for r(m,n)
Martingales and Triangle-Free Process
Exercises
Constructive Lower Bounds
Constructive Lower Bounds for r(s,t)
Constructive Lower Bounds for r(t)
A Conjecture of Borsuk
Intersecting Hypergraphs
Lower Bounds of rk(t) for k3
Exercises
Turán Number and Related Ramsey Number
Turán Numbers for Non-Bipartite Graphs
Turán Numbers for Kt,s
Erdős-Rényi Graph
Exact Values of ex(n,C4) and z(n;2)
Constructions with Forbidden K2,s
Constructions with Forbidden Kt,s
Turán Numbers for Even Cycles
Exercises
Communication Channels
Introduction
Shannon Capacities of Cycles
Connection with Ramsey Numbers
Exercises
Dependent Random Choice
The Basic Lemma
Applications
Exercises
Quasi-Random Graphs
Properties of Dense Graphs
Graphs with Small Second Eigenvalues
Some Multicolor Ramsey Numbers
A Related Lower Bound of r(s,t)
A Lower Bound for Book Graph
Exercises
Regularity Lemma and van der Waerden Number
van der Waerden Number
Recursive Bounds for wk(t)
Szemerédi's Regularity Lemma
Two Applications
Extensions on the Regularity Lemma
Exercises
More Ramsey Linear Functions
Subdivided Graphs
Ramsey Goodness
Large Books Are p-Good
Exercises
Various Ramsey Problems
Size Ramsey Numbers
Induced Ramsey Numbers
Bipartite Ramsey Numbers
Folkman Numbers
For Parameters and Coloring Types
Exercises
References
Glossary
Index
