1
$\begingroup$

The following statement is a well-known lemma of Ramsey number. $$R(m+1,n+1) \leq {m+n \choose m}$$

Now, I want to prove the improvement of the above statement: $$R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+n_2+\cdots+n_k \choose n_1,n_2,\cdots,n_k}$$

I found some references mentioning it but they just used it as an obvious 'fact'.
I tried to use an induction on $k$ or use the following lemma, $$R(p_1,\cdots,p_{c-1},p_c) \leq R(p_1,\cdots,R(p_{c-1},p_c))$$

but unfortunately, both strategies did not work well.
Would you help me?
Thanks.

$\endgroup$
2
  • 1
    $\begingroup$ The last lemma seems to rather be about hypergraph Ramsey numbers. For graphs, you get a recurrent bound which is exactly the multi-Pascal relation. $\endgroup$ Nov 25, 2021 at 18:07
  • $\begingroup$ @FedorPetrov Hmm...I searched about hypergraph Ramsey number, but I am still walking among the fog. Can you explain more details? $\endgroup$
    – okw1124
    Nov 25, 2021 at 19:53

0

Your Answer

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