🔢Ramsey Theory Unit 2 – Ramsey's Theorem – Infinite and Finite Cases

Key Concepts and Definitions

• Ramsey theory studies the conditions under which order must appear in large structures, even if that order is not immediately apparent
• Homogeneous subset is a subset of vertices in which all edges have the same color
• Ramsey number $R(r, s)$ represents the smallest number of vertices in a complete graph that guarantees a red $K_r$ or a blue $K_s$ will always be present
• Arrowing notation $A \rightarrow (B)^n_k$ denotes that for any $k$-coloring of the $n$-element subsets of $A$, there exists a subset $B \subseteq A$ such that all $n$-element subsets of $B$ have the same color
  • Commonly used in the context of Ramsey's theorem for hypergraphs
• Diagonal Ramsey numbers $R(k)$ represent the smallest number of vertices in a complete graph that guarantees a monochromatic $K_k$ will always be present, regardless of the number of colors used
• Van der Waerden numbers $W(k, r)$ represent the smallest positive integer such that any $r$-coloring of the integers $1, 2, \ldots, W(k, r)$ contains a monochromatic arithmetic progression of length $k$
• Schur numbers $S(r)$ denote the smallest positive integer such that any $r$-coloring of the integers $1, 2, \ldots, S(r)$ contains a monochromatic solution to the equation $x + y = z$

Historical Context and Development

• Ramsey theory is named after British mathematician Frank P. Ramsey, who laid the foundation for the field in his 1930 paper "On a Problem of Formal Logic"
• Issai Schur, a German mathematician, proved a special case of Ramsey's theorem in 1916, now known as Schur's theorem
• Bartel Leendert van der Waerden, a Dutch mathematician, proved a theorem about arithmetic progressions in 1927, which is now considered a central result in Ramsey theory
• Paul Erdős and George Szekeres, Hungarian mathematicians, published a paper in 1935 that introduced the concept of Ramsey numbers and provided a new proof of Ramsey's theorem
  • They also posed the "party problem," a simple and intuitive way to understand Ramsey's theorem
• The term "Ramsey theory" was coined by Theodore Motzkin in the 1950s, recognizing the growing body of work in this area
• Over the years, Ramsey theory has found applications in various fields, including combinatorics, graph theory, number theory, and theoretical computer science
• The development of Ramsey theory has led to the discovery of numerous related theorems and extensions, such as the Hales-Jewett theorem and the Graham-Rothschild theorem

Finite Ramsey Theorem

• The finite Ramsey theorem states that for any positive integers $r$ and $k$, there exists a smallest positive integer $R(r, k)$ such that any $r$-coloring of the edges of a complete graph on $R(r, k)$ vertices contains a monochromatic complete subgraph on $k$ vertices
• In simpler terms, the theorem guarantees the existence of a monochromatic complete subgraph of a certain size within any sufficiently large complete graph, regardless of how its edges are colored
• The finite Ramsey theorem can be generalized to hypergraphs, where the edges are replaced by $n$-element subsets of vertices
  • In this case, the Ramsey number $R_n(k_1, k_2, \ldots, k_r)$ represents the smallest number of vertices in an $n$-uniform hypergraph that guarantees the existence of a monochromatic complete $n$-uniform subhypergraph on $k_i$ vertices in color $i$, for some $1 \leq i \leq r$
• The finite Ramsey theorem has several interesting special cases, such as the diagonal Ramsey numbers and the van der Waerden numbers
• Computing exact Ramsey numbers is a challenging problem, with only a few known values for small parameters
  • For example, $R(3, 3) = 6$, $R(4, 4) = 18$, and $R(5, 5)$ is known to be between 43 and 48

Infinite Ramsey Theorem

• The infinite Ramsey theorem is an extension of the finite Ramsey theorem to infinite sets
• It states that for any positive integers $r$ and $k$, and any $r$-coloring of the $k$-element subsets of an infinite set $X$, there exists an infinite subset $Y \subseteq X$ such that all $k$-element subsets of $Y$ have the same color
• The infinite Ramsey theorem can be expressed using the arrowing notation as $\mathbb{N} \rightarrow (\mathbb{N})^k_r$, where $\mathbb{N}$ represents the set of natural numbers
• One of the most famous consequences of the infinite Ramsey theorem is the Erdős-Szekeres theorem on monotone subsequences
  • It states that any sequence of $(r-1)(s-1)+1$ distinct real numbers contains either an increasing subsequence of length $r$ or a decreasing subsequence of length $s$
• The infinite Ramsey theorem has applications in various areas of mathematics, including set theory, topology, and mathematical logic
• The theorem can be further generalized to partition relations on ordinals and other infinite structures

Proof Techniques and Strategies

• Proofs in Ramsey theory often involve a combination of combinatorial arguments, pigeonhole principle, and induction
• The most common proof technique for Ramsey-type theorems is the color-focusing method, which involves iteratively reducing the number of colors until a monochromatic structure is found
  • This method is used in the original proofs of Ramsey's theorem by Ramsey and Erdős-Szekeres
• The Erdős-Szekeres proof of the finite Ramsey theorem uses a double induction argument on the number of colors and the size of the desired monochromatic complete subgraph
• The proof of the infinite Ramsey theorem typically involves transfinite induction and the axiom of choice
  • One approach is to use the compactness theorem from mathematical logic to deduce the infinite case from the finite case
• Probabilistic methods, such as the Lovász local lemma and the probabilistic method, are often used to prove the existence of certain Ramsey-type structures without explicitly constructing them
• Other proof techniques used in Ramsey theory include the amalgamation method, the Hales-Jewett theorem, and the Graham-Rothschild theorem

Applications and Examples

• Ramsey theory has found applications in various areas of mathematics and theoretical computer science
• In graph theory, Ramsey-type results are used to study the existence of certain substructures in graphs, such as cliques, independent sets, and cycles
  • For example, the Ramsey number $R(3, 3) = 6$ implies that any graph on 6 or more vertices must contain either a triangle or an independent set of size 3
• In number theory, van der Waerden's theorem on arithmetic progressions is a classic example of a Ramsey-type result
  • It states that for any positive integers $k$ and $r$, there exists a smallest positive integer $W(k, r)$ such that any $r$-coloring of the integers $1, 2, \ldots, W(k, r)$ contains a monochromatic arithmetic progression of length $k$
• Ramsey theory has applications in theoretical computer science, particularly in the study of communication complexity and lower bounds for data structures
  • For instance, the Ramsey-based lower bound for the complexity of the set intersection problem shows that any deterministic protocol for this problem requires $\Omega(n)$ bits of communication
• In combinatorial game theory, Ramsey-type arguments are used to analyze the existence of winning strategies in certain games, such as the Hales-Jewett game and the Sim-Ehrenfeucht game

Related Theorems and Extensions

• Ramsey theory has inspired numerous related theorems and extensions that explore similar ideas in different contexts
• The Hales-Jewett theorem is a powerful generalization of van der Waerden's theorem, dealing with higher-dimensional combinatorial subspaces
  • It states that for any positive integers $k$ and $r$, there exists a smallest positive integer $HJ(k, r)$ such that any $r$-coloring of the $k$-dimensional combinatorial subspaces of a sufficiently large hypercube contains a monochromatic combinatorial line
• The Graham-Rothschild theorem is another far-reaching generalization of Ramsey's theorem, concerning the existence of monochromatic combinatorial subspaces in higher dimensions
• The Canonical Ramsey theorem, proved by Erdős and Rado, extends Ramsey's theorem to infinite cardinals and provides a framework for studying partition relations on uncountable structures
• The Paris-Harrington theorem is a strengthened version of the finite Ramsey theorem that is independent of the Peano arithmetic, demonstrating the connection between Ramsey theory and mathematical logic
• Other notable extensions include the Nešetřil-Rödl theorem on Ramsey classes of relational structures, the Milliken-Taylor theorem on partition regular matrices, and the Deuber-Rothschild-Sauer theorem on Ramsey properties of categories

Challenges and Open Problems

• Despite significant progress in Ramsey theory, many fundamental questions remain open, and the field continues to pose challenging problems
• Determining exact values of Ramsey numbers is a notoriously difficult problem, with only a handful of values known for small parameters
  • The classical Ramsey number $R(5, 5)$ is only known to lie between 43 and 48, and the gap between the lower and upper bounds grows rapidly for larger parameters
• The growth rate of Ramsey numbers is another major open problem, with the best-known bounds being far apart
  • Erdős famously offered a $100 prize for determining whether the limit$\lim_{n \to \infty} \frac{R(n, n)^{1/n}}{n}$ exists, and if so, for finding its value
• Finding better constructive lower bounds for Ramsey numbers is an ongoing challenge, as most lower bounds are obtained through probabilistic arguments that do not provide explicit constructions
• Generalized Ramsey numbers, such as the multicolor Ramsey numbers and the off-diagonal Ramsey numbers, are even less well-understood than the classical Ramsey numbers, with many open questions regarding their asymptotic behavior
• The study of Ramsey properties of infinite structures, such as graphs and hypergraphs on uncountable vertex sets, is a rapidly developing area with numerous open problems and potential applications to set theory and mathematical logic