ریمزی نظریہ

اصطلاح	term
ریمزی نظم و ضبط شرائط	Ramsey order conditions

ریاضیات میں ریمزی نظریہ وہ شرائط بتاتا ہے جس کے تحت مسائل میں نظم و ضبط لازماً پایا جائے گا۔ ریمزی نظریہ کا فلسفہ یہ ہے کہ اگر کوئی نظام کافی بڑا ہو تو کتنا ہی تصادفی کیوں نہ ہو، اس میں ایسے ضمنی نظام لازماً ہوں گے جن میں ترتیب پائی جائے گی۔ مثلاً 6 افراد کے گروہ میں لازماً 3 افراد پر مشتمل ضمنی گروہ ہو گا جس میں ہر جوڑا آپس میں مانوس ہو یا پھر 3 افراد کا ضمنی گروہ ہو گا جس میں ہر جوڑا باہمی اجنبی ہو۔

فائل:Ramsey633 graph.png

تصویر 1۔ K₆ کا رنگنا، جس میں ہم رنگی K₃ موجود ہیں۔

اس مثال کو ہم یوں بھی بیان کر سکتے ہیں: فضاء میں چھ نکات ہیں (کوئی تین ایک لکیر میں نہیں اور کوئی چار مستوی میں نہیں)۔ ہر دو نکات کے جوڑے کو ملانے والی 15 لکیروں میں سے کچھ کو سرخ رنگ کیا جاتا ہے اور کچھ کو نیلا رنگ۔ اس تصویر میں لازمی طور پر کم از کم ایک ہم رنگ (نیلا یا سرخ) تکون موجود ہو گا۔

جامع تعریف: چلو p اور q دو مثبت صحیح عدد ہوں۔ ایک مثبت عدد r کو $\ -(p,q)$ریمزی خاصہ کہیں گے اگر r افراد کے کسی بھی گروہ میں یا تو p افراد پر مشتمل ایسا ضمنی گروہ ہو جس میں تمام افراد ایک دوسرے سے مانوس ہوں یا پھر q افراد پر مشتمل ایسا گروہ ہو جس میں تمام افراد ایک دوسرے سے اجنبی ہوں۔ عدد r کی کم سے کم ایسی قدر کو ریمزی عدد کہتے ہیں اور علامتی طور پر اسے یوں لکھتے ہیں: $\ R(p,q)=r$ ریمزی نظریہ کے مطابق مناسب بڑے عدد r کو ریمزی خاصہ ہمیشہ حاصل ہو گا۔

K₅ کا رنگنا، جس میں کوئی ہم رنگی K₃ موجود نہیں۔

ثبوت کہ $\ R(3,3)=6$

1. پہلے ہم ثابت کرتے ہیں کہ $\ R(3,3)\leq 6$

6 افراد کا گروہ (الف، ب، ج، د، ل، ک) ہے۔ فرض کرو کہ الف سے مانوس افراد کمرہ #1 میں بیٹھے ہیں اور الف سے اجنبی افراد کمرہ #2 میں بیٹھے ہیں جبکہ الف کسی کمرے میں نہیں۔ اب ان میں سے ایک کمرے میں کم از کم 3 افراد لازمی ہیں۔ فرض کرو کہ یہ کمرہ #1 ہے۔ یا تو ان 3 افراد میں سب اجنبی ہیں (اور ہمارا بیان درست ہے) یا ان میں سے کم از کم 2 افراد ایک دوسرے سے مانوس ہیں جس صورت میں الف اور یہ دو افراد آپس میں مانوس ہیں (اور ہمارا بیان پھر درست ہے)۔

اسی طرح اگر کم از کم 3 افراد والا کمرہ 2# ہو، تو ہم اوپر والی منطق کو پھیر کر بیان ثابت کر سکتے ہیں۔

1. اب ہم دکھاتے ہیں کہ $\ R(3,3)>5$

فرض کرو کہ یہ 5 افراد ایک دائرہ میں بیٹھے ہیں اور ہر فرد صرف اپنے دائیں اور بائٰیں بیٹھے فرد سے مانوس ہے۔ اس لیے کوئی ایسے 3 افراد نہیں جو آپس میں مانوس ہوں اور ایسے 3 افراد کا ضمنی گروہ بھی نہیں جن میں کوئی ایک دوسرے کو نہ جانتا ہو۔

R(m,n)=R(n,m)

R(m,1)=1

R(m,2)=m

R(3,3)=6

R(4,3)=9

R(5,3)=14

R(4,4)=18

ریمزی عدد پر حدور

• m اور n صحیح اعداد ہوں، دونوں 2 سے بڑے، تو

$R(m,n)\leq R(m-1,n)+R(m,n-1)$

• m اور n صحیح اعداد ہوں، دونوں 1 سے بڑے، تو

$R(m,n)\leq {\binom {m+n-2}{m-1}}$

بیرونی روابط

• en:Ramsey's theorem (انگریزی وکیپیڈٰیا)
• RAMSEY'S THEOREM AND RAMSEY THEORYآرکائیو شدہ بذریعہ math.unh.edu

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات