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