12
$\begingroup$

There are few results in modern mathematics that I find so deep and full of philosophical implications as Ramsey's theorem.

I am aware (at some basic level) that it has generated a plethora of further research, going well beyond graph theory, and that there is now an entire industry of Ramsey-like theorems, in many disparate domains (for instance enumerative combinatorics).

What troubles me, though, is that I do not clearly see what the proper framework for a generalized Ramsey Theory could possibly be.

If you browse the wiki, you find the following sentence, under the voice RAMSEY THEORY:

Problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?"

That sound general enough, but a little too informal:

can this sentence be re-formulated in a rigorous way?

I mean: categories of structured sets are the bread-and-butter of category theory (think for instance of categories of algebras, categories of ordered sets, etc), so it looks to me as if there could be a convenient formulation of the quoted sentence in suitable categorical form

(something like: if .... then for every object of the category there is a large -in some suitable sense- sub-object satisfying ....., fill the dots)

Anything out there?

$\endgroup$
3
  • 1
    $\begingroup$ Should I mention combinatorial species here? $\endgroup$
    – David Roberts
    Jan 13, 2013 at 18:04
  • $\begingroup$ David, yes you should mention them ! In fact, I was thinking of what Joyal did for general combinatorics with the Theory of Species, as perhaps a possible baseline for what I ask for here $\endgroup$ Jan 13, 2013 at 19:17
  • $\begingroup$ Mirco, have you looked at Ramsey's original paper? His lemma was used in mathematical logic firstly, and the initial generalizations were to larger cardinalities (if memory serves). If his original paper does not satisfy your requirements, perhaps you could add some clarifying remarks to your question. (If the idea is to do some unification of the various flavors appearing in combinatorics, I might sort of understand, maybe.) If you are only looking for a categorical version, you need to make that clear. Gerhard "Thinks Original Ramsey Already General" Paseman, 2013.01.13 $\endgroup$ Jan 13, 2013 at 22:02

3 Answers 3

11
$\begingroup$

I do not really understand the motivation behind the question. Ramsey's Theorem is just a very beautiful piece of mathematics, and there is no need to generalize it in terms of category theory just for the sake of generalization. On the other hand, the note Ramsey Theory by R. L. Graham and B. L. Rothschild discusses categorical generalizations.

Let $C$ be a category (which should be well-powered). For objects $N,K \in C$ denote by $\binom{N}{K}$ set of subobjects of $N$ of the form $K \to N$. Every monomorphism $\phi : L \to N$ induces a map $\tilde{\phi} : \binom{L}{K} \to \binom{N}{K}$. The category $C$ is called Ramsey if for every positive integer $r$ ("number of colors") and all objects $K,L \in C$ there is an object $N \in C$ ("Ramsey number") such that for every map $c : \binom{N}{K} \to [1,r]$ ("coloring") there exists a monomorphism $\phi : L \to N$ and some $i \in [1,r]$ such that the diagram

$$\begin{matrix} \binom{N}{K} & \xrightarrow{c} & [1,r] \\\\ {\small \tilde{\phi}} \uparrow ~ & & \uparrow \\\\ \binom{L}{K} & \xrightarrow{ } & \{i\} \end{matrix}$$

commutes ("there is a complete monochromatic subgraph on $L$ vertices").

For the category of finite sets and with injections as morphisms this is precisely Ramsey's classical Theorem (the case $K=2$ being about graphs). For the category of finite-dimensional vector spaces over a finite field one discovers Rota's conjecture, which is proven over $\mathbb{F}_2,\mathbb{F}_3,\mathbb{F}_4$, but otherwise unknown. This already indicates how hard it will be to test the Ramsey property of other categories.

See also the paper Ramsey's Theorem for a class of categories by Graham, Leeb, Rotschild.

$\endgroup$
5
  • $\begingroup$ Martin, thanks for the ref! As for the motivation behind, well, what I do need is this: Ramsey's result is not just a beautiful piece of math, which it certainly is, but a true REVOLUTION in math (and in fact, it literally originated an entire industry with no end in sight). What is more, it is a very DEEP result, which has a philosophical interest, namely the discovery that order can emerge out of chaos just by sheer numbers.. anyway, my point is: WHAT EXACTLY IS RAMSEY'S THEORY? what is its general framework? I do not necessarily think this framework should be categorical, only cat theory is $\endgroup$ Jan 13, 2013 at 19:21
  • $\begingroup$ perhaps the best starting point to provide such a framework. But I would be happy with something else, as long as it makes formal the general (and generic statement) I have put in bold. $\endgroup$ Jan 13, 2013 at 19:23
  • 2
    $\begingroup$ Why is this Rota's conjecture? $\endgroup$
    – Will Sawin
    Jan 13, 2013 at 19:45
  • 1
    $\begingroup$ Isn't this explained in the article? $\endgroup$ Jan 26, 2013 at 12:15
  • 1
    $\begingroup$ Which article? The wikipedia page you linked to and the the note you linked to seem naively to describe different conjectures by Rota, and I have not yet found an explanation of why they are in fact the same conjecture. In particular, the note seems to suggest that the conjecture has in fact been proven. $\endgroup$
    – Will Sawin
    Feb 18, 2013 at 6:22
7
$\begingroup$

You might be interested in the 2010 book "Introduction to Ramsey Spaces" by Stevo Todorcevic

"Ramsey theory is a fast-growing area of combinatorics with deep connections to other fields of mathematics such as topological dynamics, ergodic theory, mathematical logic, and algebra. The area of Ramsey theory dealing with Ramsey-type phenomena in higher dimensions is particularly useful. Introduction to Ramsey Spaces presents in a systematic way a method for building higher-dimensional Ramsey spaces from basic one-dimensional principles. It is the first book-length treatment of this area of Ramsey theory, and emphasizes applications for related and surrounding fields of mathematics, such as set theory, combinatorics, real and functional analysis, and topology. In order to facilitate accessibility, the book gives the method in its axiomatic form with examples that cover many important parts of Ramsey theory both finite and infinite."

$\endgroup$
3
$\begingroup$

"Complete disorder is impossible" T. Motzkin

Every large system contains a large well organized subsystem.

"How large" can be a great question (assuming we take it to mean large finite) but just showing that a certain class of systems has this property seems deeper to me. I find the audacity of the induction involved stunning. Sometimes the cleanest path to finite results is to replace "large" by "infinite", prove that result, and then concluded that the finite results hold. Some results are deep, in part, because we talk about sizes in ranges we need novel notation to even mention.

$\endgroup$
1
  • $\begingroup$ Aaron, yes, Motzkin 's mantra is exactly why Ramsey's theory is such a huge contribution to our understanding of the world. I gave you my like, because you gave some philosophical context to my question. However, what I am after here is: how can I make a general formal framework for this theory? Martin's answer goes some way in that direction.... $\endgroup$ Jan 13, 2013 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.