0
$\begingroup$

The Ramsey number is stated, where $R(2,3)$ means Ramsey number where there exists a monochromatic clique of size 2 or a monochromatic clique of size 3.

I also came to understand that $R(2,3) = N(2,3;2)$

What does $N(2,3;3)$ mean? Especially I do not understand what the 3 means after ;

Regarding this I came across the previous post: Ramsey Number R(4,4), that one user described as:

$N(m,n;k)$ is the generalized Ramsey's number $R(m,n)$ , except for k colors.

Can someone shine some light on what multicolor ramsey notation $N(m,n;k)$ actually means?

$\endgroup$
  • $\begingroup$ See that user's subsequent comment. $\endgroup$ – Angina Seng Apr 5 '19 at 6:52
  • $\begingroup$ @LordSharktheUnknown by "the size of colored subsets" does he mean monochromatic $K_k$? So confused. $\endgroup$ – hiam Apr 5 '19 at 6:56
2
$\begingroup$

The notation $N(m,n,k)$ does not refer to generalized Ramsey number.

The notation $N(q_1,\ldots,q_s;r)$ refers to a specific case, where you start with a set $S$ of size $n$, and all ($\binom{n}{r}$-many) $r$-subsets of $S$ are split into $s$ mutually exclusive families (i.e. $s$ colors). Then a theorem states if $n \geq N(q_1, q_2,\ldots,q_s; r)$ there is an $i\leq s$, and some $q_i$-subset of $S$ for which every $r$-subset is monochromatic.

With $r=2$, this is just looking at a coloring of the edges. Hence an equivalence with Ramsey number. As soon as you have $r>2$, you are looking at complete $r$-uniform hypergraphs , and coloring of their multi-edges.

See Thereoem 3.3 p28 of this Course for details.

Generalized Ramsey number are in the form $R(q_1,q_2,\ldots,q_k)$ and means that for any $k$-coloring of $K_n$ with $n\geq R(q_1,q_2,\ldots,q_k)$ there exist a monochromatic $K_{q_i}$ for some $i$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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