The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.
Special thanks to Ivan Khatchatourian for clarifying some typos and adding some elaborations.
Title: Ramsey and Ultrafilter 1 (of 2)
Lecturer: Slawomir Solecki
Date: Wednesday October 19, 2016.
Main Topics: Gowers’ Theorem, Lupini’s Theorem, Furstenberg-Katznelson Theorem, Monoids, Semigroups.
Lecture 1 – Lecture 2
You might also be interested in Solecki’s independent lecture about projective Fraisse limits [link soon].
We will look at three related Ramsey results: Gowers’ Theorem, Lupini’s generalization and Furstenberg-Katznelson. These theorems all use the technology of (partial) semigroups and idempotent ultrafilters. We will introduce the relevant technology and then work towards a general statement that captures all three theorems. To do this we introduce language and notions from Monoid theory.
The second lecture will look at the proofs of these theorems.
The following references are useful in understanding the ideas that go into these proofs:
The three big theorems
Definition. Let be an alphabet (usually taken to be ). A located word is a finite partial function from to . Given two located words we say that iff .
When we write the concatenation for .
Denote by the words in . In the (common) case that we denote .
The Tetris operator where if and . We may extend this to act on words by taking .
We denote repeated applications of on a word by .
We are now in a position to state Gowers’ theorem. In short it is a Ramsey result about the structure of repeated applications of to different sections of a word.
Note that if the minimum is , then there are no applications of the Tetris operator, so all these words have the same colour.
There is also a hereditary version of Gowers’ Theorem that guarantees the existence of monochromatic block subspaces.
Definition. Fix words such that .
We now prepare to state Lupini’s generalization of this. The generalization focuses on generalizing the Tetris operator to any 1-Lipschitz maps.
Equivalently, is the collection of non-decreasing surjections onto for some . Equivalently, it is the collection of non-decreasing -Lipschitz functions from to .
Note that the Tetris operator is in .
Lupini noticed that his proof did not extend to the hereditary version, and asked the following question:
We’ll discuss this example later, but it is the function that sends to (and each “tooth” is a ). There is a 2-colouring of such that no (with ), is the set is monochromatic.
Notice that the max is stabilized.
“This theorem doesn’t get so much press.”
Definition. Let be disjoint finite sets. Let .
The word is the word achieved by first removing all letters in , then replacing each string of a repeated letter with a single instance of .
We will now set the alphabet where is a placeholder not it . For let be the word in obtained by substituting the letter for every occurrence of .
This is meant to capture the notion of “type” that the colouring will depend on. In the earlier theorems it was captured by or .
If you only draw your substitutions from , then is always the empty word. This yields the infinite Hales-Jewett theorem (taking .)
There is an example where the theorem is false if the set is infinite.
Monoids and semigroups
Now the goal is to find an abstract setting for all three of these theorems. We draw language from semigroups and monoids.
Definition. A partial semigroup is a set with a partially defined, associative binary operation . We will assume our partial semigroups are directed, that is such that is defined for all .
A (finite) monoid is a set with an associative (fully defined) binary operation and identity element denoted .
A monoid acts on a partial semigroup if
- for all ,
- , for all and .
- if is defined, then is defined equal to .
- if is defined, then is defined.
The first two conditions are the usual “action” conditions, and the third and fourth are required because we only have a partial semigroup.
Our monoids will usually resemble the Tetris operator.
Gowers’. Here and are the elements of the desired monoid. .
Lupini. with composition, and it acts letter by letter. (Exercise. Show that this is a monoid.)
Furstenberg-Katznelson. This one is slightly more complicated, but completely illustrates the correct abstraction.
, where is just a helpful placeholder. Define the operation as follows:
- for all
- for all
- for all .
Notice that elements of and behave differently. acts on words in by substitution for and left multiplication on other letters.
This helps us describe some Ramsey behaviour.
It turns out that Lupini’s example is not Ramsey, but behaves like Ramsey. (We’ll explain more below.)
Some definitions from monoid theory
Fix a finite monoid .
Definition. Define the collection of ideals , and give it the partial order . (This object isn’t that complicated, usually it’s or with an added point.)
acts on by , and is order preserving.
For a fixed , the R-class of is the set . (This is an equivalence class.)
is R-trivial if each R-class has only one element.
is almost R-trivial if for each whose R-class has more than one element we have for all .
The idea for almost R-trivial is that “you can have more than one element in each R-class, but they must be of a specific type.”
The structure of
In the case of almost R-trivial, Ramsey is equivalent to the geometric structure of .
Even in the case where we can still get “traces of Ramsey”.
Gowers’. This is linear with .
Furstenberg-Katznelson. This is not linear. is on top, it is above all elements of (which form an antichain) and there is a single point for all of below everything. (Exercise Prove this.)
“You extract the type from this poset.”
Lupini. Here , for . are all lines. For we get a cycle as follows:
Bergelson-Blass-Hindman realized we could use ultrafilter methods on partial semigroups. Here we introduce some basic topological notions and the key lemma.
Definition. Let be a partial directed semigroup.
is the collection of all ultrafilters on such that . (This is exactly where we need that the partial semigroup is directed.)
iff iff . In the third part we are using ultrafilter quantification: means such that . This is reminiscent of measure theory where we say “for all in a measure 1 set”.
The topology on is generated by sets of the form , where . Here is a compact left topological semigroup (i.e. multiplication on the left is left continuous).
This gives us the following fundamental theorem.
Definition. Call an idempotent element of if .
Let be the collection of all idempotent elements of .
If acts on by endomorphisms, then acts on by continuous automorphisms where iff .
Note that for all .