For any set , denote by the collection of 2-subsets of .

**Ramsey Theorem.** For any colouring of with two colours there exists an infinite subset such that is monochromatic.

It seems to me that a good question is: has Ramsey theorem anything to do with the ultrafilter monad? I think so, but I also believe category theory experts might be much faster than me to give an answer. First a link to some course notes on Ramsey theory, to know what I am speaking about. Also this post might be helpful (the link to the notes is from a comment there).

The proof of Ramsey theorem uses (basically only) the infinite pigeonhole principle. It’s finitary version uses a nonprincipal ultrafilter. The proofs are easy to follow. Now, the infinite pigeonhole principle is the same as saying that with the usual coproducts is a monoidal category. This fact makes the collection of all infinite sets to have the partition regularity property which is equivalent with the infinite pigeonhole principle.

Moreover, the conclusion of Ramsey theorem can be stated as the partition regularity property of another collection of sets.

**Question 1:** What is the relation between the (complementaries of these) collections from a categorical pov? (both should be monoids, how are they related?)

The proof of the finitary version of Ramsey theorem uses ultrafilters, but ultrafilters are also related to the inclusion by the intermediary of the ultrafilter monad, here is a reference http://arxiv.org/abs/1209.3606.

The ultrafilter monad is a monoid in the category of endofunctors of .

**Question 2:** How is the ultrafilter monad related to these monoids from question 1?

Now, I bet that both Ramsey theorem and it’s finitary version (as well as the other Ramsey-type theorems from R. Graham, K. Leeb, and B. Rothschild, Ramsey’s Theorem for a class of categories, Advances in Math. 8 (1972), 417-433.) can be expressed by answering to these questions, i.e. by using only this structure: , it’s monoidal structure and the ultrafilter monad. Can anybody do it? (If true, this could be relevant for understanding better the theorem, it would also tell that this categorical structure may be more relevant than the one based on monomorphisms of Graham et al.)

In my opinion this is a low hanging fruit for category theorists which might help combinatorialists (by making them believe category theory has something to say, even if it seems so up in the sky).

### Like this:

Like Loading...

*Related*

Welcome to the paradoxical world of the Pigeonhole Principle! I like the discussion of ultrafilters here http://www.umsu.de/wo/2012/577 , but it does not address the monoid question directly. The biggest obstacle seems to be the lack of a unified formal way of defining the problem.

I can do it, but it takes time (from doing other stuff which uses this), so I thought I could ask the experts. This seemed to work, in the past, with mathoverflow, but this time my question is not sufficiently clear to put it there. The matter is exactly that of making it clear, because I bet that once is clear then it will be almost obvious. And that is nice, because it would provide (unless I’m dreaming) another categorical treatment of some Ramsey-type theorems than the classic Graham et al.

Btw, I thought about you when pondering with the partition regularity, first I tried to see if there’s something in lattices and Stone duality is a natural tool to use, but after I just realized it has to be a matter purely involving monads, monoids, you have a theorem which uses one monoid(al) thing as a tool to prove the conclusion that another thing is monoidal as well, to conclude (for the finitary version) by using a very special monad, etc. So, I have hope and waiting for an answer.