Menu Close

Prove-that-R-m-n-C-m-n-m-Here-R-states-the-Ramsey-theory-

Tinku Tara 0 Comments
Pin




Question Number 186285 by Shrinava last updated on 03/Feb/23
Prove that: R (m , n) ≤ C_(m+n) ^m Here R states the Ramsey theory
$$\mathrm{Prove}\:\mathrm{that}: \\ $$$$\mathrm{R}\:\left(\mathrm{m}\:,\:\mathrm{n}\right)\:\leqslant\:\mathrm{C}_{\boldsymbol{\mathrm{m}}+\boldsymbol{\mathrm{n}}} ^{\boldsymbol{\mathrm{m}}} \\ $$$$\mathrm{Here}\:\:\mathrm{R}\:\:\mathrm{states}\:\mathrm{the}\:\:\mathrm{Ramsey}\:\:\mathrm{theory} \\ $$
Commented by mr W last updated on 03/Feb/23
R(m,n)≤R(m−1,n)+R(m,n−1) R(m,n)≤ (((m+n−2)),((m−1)) ) = (((n+m−1)),(m) )− (((n+m−2)),(m) ) = (((n+m)),(m) )− (((n+m−1)),((m−1)) )− (((n+m−2)),(m) ) ≤ (((n+m)),(m) )
$${R}\left({m},{n}\right)\leqslant{R}\left({m}−\mathrm{1},{n}\right)+{R}\left({m},{n}−\mathrm{1}\right) \\ $$$${R}\left({m},{n}\right)\leqslant\begin{pmatrix}{{m}+{n}−\mathrm{2}}\\{{m}−\mathrm{1}}\end{pmatrix} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\begin{pmatrix}{{n}+{m}−\mathrm{1}}\\{{m}}\end{pmatrix}−\begin{pmatrix}{{n}+{m}−\mathrm{2}}\\{{m}}\end{pmatrix} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\begin{pmatrix}{{n}+{m}}\\{{m}}\end{pmatrix}−\begin{pmatrix}{{n}+{m}−\mathrm{1}}\\{{m}−\mathrm{1}}\end{pmatrix}−\begin{pmatrix}{{n}+{m}−\mathrm{2}}\\{{m}}\end{pmatrix} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\leqslant\begin{pmatrix}{{n}+{m}}\\{{m}}\end{pmatrix} \\ $$
Commented by Shrinava last updated on 03/Feb/23
perfect dear professor thank you so much
$$\mathrm{perfect}\:\mathrm{dear}\:\mathrm{professor}\:\mathrm{thank}\:\mathrm{you}\:\mathrm{so}\:\mathrm{much} \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *