What does $N(q_1, q_2, ... , q_s ; r)$ mean in van Lint's stating of Ramsey's Theorem?

Question

I've started reading van Lint and Wilson's A Course in Combinatorics and on Theorem 3.3 (Ramsey's Theorem) they use the notation $N(q_1, q_2, ... , q_s ; r)$ without an explanation prior to it. Can someone explain what this meant? I would also appreciate an explanation on what the $q_i$'s and the $r$ referred to in $N(q_1, q_2, ... , q_s ; r)$. Below is how the theorem was stated.

Theorem 3.3. Let $r \ge 1$ and $q_i \ge r, i = 1,2,...,s$ be given. There exists a minimal positive integer $N(q_1, q_2, ... , q_s ; r)$ with the following property. Let $S$ be a set with n elements. Suppose that all $n \choose{r}$ $r$-subsets of $S$ are divided into $s$ mutually exclusive families $T_1,T_2,...,T_s$ ("colors"). Then if $n \ge N(q_1, q_2, ... , q_s ; r)$ there is an $i, 1\le i \le s$, and some $q_i$-subset of $S$ for which every $r$-subset is in $T_i$.

Answer 1

The theorem in fact gives the definition of $N(q_1, q_2, ... , q_s ; r)$! It is just the number whose existence is guaranteed by the theorem.

To amplify: I expect you have seen the following as it is probably the simplest question in Ramsey theory.

Show that if the edges of the complete graph on $6$ vertices are coloured red or blue in any way whatsoever, there will always be either a red triangle or a blue triangle.

We can rephrase this as a "problem to find" rather than a "problem to prove".

Find the smallest $n$ with the following property: if the edges of $K_n$ are coloured red or blue in any way whatsoever, there will always be either a red triangle or a blue triangle.

The answer is of course $n=6$, and we express this by the equation $N(3,3;2)=6$.

This can be generalised in a number of ways. We could ask:

Find the smallest $n$ with the following property: if the edges of $K_n$ are coloured red or blue in any way whatsoever, there will always be either a $K_3$ with all edges red or a $K_5$ with all edges blue.

The least such $n$ is denoted $N(3,5;2)$; in fact it is known that $N(3,5;2)=14$. Next, suppose that we have three colours: for example,

$N(5,6,7;2)$ is the smallest $n$ with the following property: if the edges of $K_n$ are coloured red, blue or green in any way whatsoever, there will always be either a $K_5$ with all edges red or a $K_6$ with all edges blue or a $K_7$ with all edges green.

The parameter $2$ at the end of all these $N$s can also be generalised, though the concept is rather more difficult to grasp. The reason we have written a $2$ so far is that an edge of a graph can be identified with a $2$-element subset of its vertices. So our basic Ramsey theory question can be expressed as

Show that if the $2$-element subsets of a $6$-element set are coloured red or blue in any way whatsoever, there will always be either a $3$-element subset in which every $2$-element subset is red or a $3$-element subset in which every $2$-element subset is blue.

Think about this carefully until you can see that it is really nothing more than a different way of writing the first problem. Our most recent example would be

$N(5,6,7;2)$ is the smallest $n$ with the following property: if the $2$-element subsets of an $n$-element set are coloured red, blue or green in any way whatsoever, there will always be either a $5$-element subset in which every $2$-element subset is red or a $6$-element subset in which every $2$-element subset is blue or a $7$-element subset in which every $2$-element subset is green.

And then we can consider, say, $4$-element subsets instead of $2$-element subsets.

$N(5,6,7;4)$ is the smallest $n$ with the following property: if the $4$-element subsets of an $n$-element set are coloured red, blue or green in any way whatsoever, there will always be either a $5$-element subset in which every $4$-element subset is red or a $6$-element subset in which every $4$-element subset is blue or a $7$-element subset in which every $4$-element subset is green.

Since the "colouring" analogy is now rather hard to visualise - note that it is the set that is coloured, not the elements of the set - we tend to speak of "dividing $r$-element subsets into mutually exclusive families", and this gives the statement of the theorem.

It is hard to get your head around all this logic but take it easy, starting with the simplest examples, and see how you go.