Has Ramsey theorem anything to do with the ultrafilter monad?

For any set M, denote by M^{(2)} the collection of 2-subsets of M.

Ramsey Theorem. For any colouring of \mathbb{N}^{(2)} with two colours there exists an infinite subset M \subset \mathbb{N} such that M^{(2)} 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 Finset \subset Set 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 Finset \subset Set  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 Set.

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: Finset \subset Set, 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).

Advertisements

3 thoughts on “Has Ramsey theorem anything to do with the ultrafilter monad?”

    1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s