Approaching Ramsey theory in a unified way

212 Views Asked by At

Ramsey theory consists of seemingly diverse results like van der Waerden theorem and Ramsey theorem. There does not seem any apparent connection between these beyond the usual "Order within disorder" idea.

I have read that a unified approach to Ramsey theory is possible through studying chromatic number of hypergraphs. But I have not found any good references for the same. Can someone suggest some?

Also what are some other unified approaches to Ramsey theory? I also recall category theory was one of them but again I have no references for the same.

1

There are 1 best solutions below

0
On

There is a way of expressing some - but certainly not all - theorems of Ramsey theory in terms of chromatic numbers of hypergraphs. The idea is that you begin with a theorem which says that, in every finite partition of $\mathbb{N}$, one piece contains a set from a particular class of "goal" sets. For example, in Ramsey's theorem for exponent 2, the "goal" sets are exactly the sets of the form $[X]^2$ for some infinite $X \subseteq \mathbb{N}$.

We can form a hypergraph whose vertices are exactly the natural numbers, and whose hyperedges are exactly the "goal" sets. In the case of Ramsey's theorem, this means that each hyperedge will have infinitely many vertices.

Ramsey's theorem states that every finite coloring of the natural numbers has some monochromatic goal set. Translated into graph theoretic language, this says that in any finite coloring of the associated hypergraph, there is a monochromatic hyperedge - a hyperedge all of whose vertices are the same color. Hence the corresponding hypergraph does not have a finite chromatic number. In some sense, we are taking a double negation of the original theorem: a Ramsey-like result would assert the existence of a monochromatic hyperedge in any finite coloring, and the statement that the chromatic number is infinite asserts the same thing: there is not a finite coloring in which every hyperedge is not monochromatic.

This approach does allow for stating many theorems in a similar way, by merely varying the goal set and thus the set of hyperedges. But it is not really a productive way to prove new results about Ramsey theory. There is no reason that stating a theorem such as Hindman's theorem in term of hypergraphs will make it easier to prove.

There are two true "unifying" frameworks for Ramsey theory, in my opinion. Neither can prove all the results, but each one allows us to see commonalities between many results, and gives a common set of proof techniques that allows us to generalize theorems.

The first framework uses ultrafilters, and in particular uses $\beta N$, the Stone-Cech compactification of the naturals. Actually $\beta N$ is a compact right topological semigroup. One reference for this is "Algebra in the Stone-Cech Compactification" by Hindman.

The second framework uses dynamical systems and ergodic theory. The classical reference for this is "Recurrence in ergodic theory and combinatorial number theory" by Furstenburg, which is still a good introduction. There are more recent references that have more powerful results.