Possibly alternative definition of Ramsey numbers?

81 Views Asked by At

On this presentation, the definition of Ramsey numbers seems to vary from the very understandable Wikipedia explanation for $2$-colorability of the edges of a complete graph resulting in red or blue cliques of a certain size.

Instead, they are defined as follows:

$r_k(n)$ is the minimal $N$ such that every $2$-coloring of the $k$-sets of an $N$-set contains a monochromatic $n$-set.

I have no idea what $k$-set they are referring to. It is possible that the choice of the letter $k$ is due to the nomenclature for complete graphs as $K_n$ (for $n$ vertices).

There is little doubt that the definition given is equivalent, but how is reconciles with the usual $R(r,s)$ for red clique on $r$ vertices or a blue clique on $s$ vertices?

1

There are 1 best solutions below

4
On BEST ANSWER

Jacob is talking about hypergraphs, where instead of edges (connecting two vertices) we have "hyperedges" connecting $k$ vertices simultaneously. The number $r_2(n)$ (in his notation) is equal to $R(n, n)$ (in your other notation).