Erdős–Szemerédi theorem
ریاضی کے امتزاج میں، ایرڈس-زیمیرڈی تھیوریم بیان کرتا ہے کہ انٹیجرز کے ہر محدود سیٹ کے لیے، کم از کم ایک، جوڑی کے لحاظ سے جملوں کا سیٹ یا، جوڑی کے لحاظ سے مصنوعات کا سیٹ نمایاں طور پر بڑا سیٹ بناتا ہے۔ مزید واضح طور پر، ایرڈس-زیمیرڈی تھیوریم بیان کرتا ہے کہ مثبت مستقلات c موجود ہیں اور ایسے کہ کسی بھی غیر خالی سیٹ کے لیے۔ یہ 1983 میں پال ایرڈس اور اینڈری زیمیرڈی نے ثابت کیا تھا۔ اشارے سیٹ کی بنیادی حیثیت کی نشاندہی کرتے ہیں۔ جوڑی کے لحاظ سے رقم کا مجموعہ ہے اور اسے رقم کا مجموعہ کہا جاتا ہے۔ جوڑی کے لحاظ سے مصنوعات کا مجموعہ ہے اور اسے پروڈکٹ کا مجموعہ کہا جاتا ہے۔ تھیوریم اس اصول کا ایک ورژن ہے کہ اضافی ساخت اور ضرب کی ساخت ایک ساتھ موجود نہیں ہو سکتی۔ اسے اس دعوے کے طور پر بھی دیکھا جا سکتا ہے کہ حقیقی لکیر میں کوئی سیٹ نہیں ہوتا جو ایک محدود ذیلی رنگ یا محدود ذیلی فیلڈ سے مشابہت رکھتا ہو۔ یہ اس کی پہلی مثال ہے جسے اب سم پروڈکٹ رجحان کے نام سے جانا جاتا ہے، جو اب محدود فیلڈز سمیت مختلف قسم کے رنگوں اور فیلڈز میں رکھنے کے لیے جانا جاتا ہے۔ سم پروڈکٹ قیاس سم پروڈکٹ قیاس غیر رسمی طور پر کہتا ہے کہ کسی بھی سیٹ کے سم سیٹ یا پروڈکٹ سیٹ میں سے ایک تقریبا جتنا ممکن ہو اتنا بڑا ہونا چاہیے۔ یہ اصل میں ایردوس اور زیمیردی نے انٹیجرز کے بارے میں قیاس کیا تھا، لیکن خیال کیا جاتا ہے کہ یہ حقیقی اعداد پر قائم ہے۔ قیاس: کسی بھی سیٹ کے لیے ایک ہے o (1) نوٹیشن میں ایسمپٹوٹک پیرامیٹر |A | ہے۔ مثالیں اگر پھر غیر علامتی اشارے کا استعمال کرتے ہوئے، غیر علامتی پیرامیٹر کے ساتھ۔ غیر رسمی طور پر، یہ کہتا ہے کہ کا مجموعہ نہیں بڑھتا ہے۔ دوسری طرف، پروڈکٹ کا سیٹ سب کے لیے فارم کی حد کو پورا کرتا ہے۔ اس کا تعلق ایرڈس ضرب ٹیبل کے مسئلے سے ہے۔ اس سیٹ کے لیے سب سے بہترین نچلی حد کیون فورڈ کی وجہ سے ہے۔ یہ مثال فیو سمز، گیورگی الیکس اور امری زیڈ روزسا کے سم پروڈکٹ مسئلے کے بہت سے پروڈکٹس ورژن کی ایک مثال ہے۔ ان کے نتیجے کا نتیجہ یہ ہے کہ چھوٹے اضافی ڈبلنگ کے ساتھ کوئی بھی سیٹ، مثال کے طور پر ریاضی کی ترقی پروڈکٹ سیٹ پر نچلی حد رکھتی ہے۔ زو اور چاؤ نے ثابت کیا کہ انٹیجرز میں ریاضی کی ترقی کے کسی بھی گھنے ذیلی سیٹ کے لیے، جو کہ ایکسپوینٹ میں موجود عنصر تک تیز ہے۔ اس کے برعکس، سیٹ مطمئن کرتا ہے، لیکن اس میں بہت سے مجموعے ہوتے ہیں: یہ باؤنڈ کسی نمبر کی بائنری نمائندگی پر غور کرنے سے آتا ہے۔ سیٹ ہندسی ترقی کی ایک مثال ہے۔ اعداد کے بے ترتیب سیٹ کے لیے، پروڈکٹ سیٹ اور سم سیٹ دونوں میں کارڈینالیٹی ہوتی ہے ؛ یعنی، زیادہ امکان کے ساتھ سم سیٹ کوئی بار بار عناصر پیدا نہیں کرتا، اور پروڈکٹ سیٹ کے لیے بھی ایسا ہی ہوتا ہے۔ قیاس آرائی کی شدت ایرڈس اور زیمیرڈی باؤنڈ کے ساتھ انٹیجرز کے کافی ہموار سیٹ کی مثال دیتے ہیں: اس سے پتہ چلتا ہے کہ قیاس میں او (1) اصطلاح ضروری ہے۔ غیر معمولی معاملات کا اکثر مطالعہ مفروضے کے انتہائی معاملات ہوتے ہیں: چند رقوم، بہت سے پروڈکٹ (ایف ایس ایم پی): اگر، تو چند مصنوعات، بہت سے رقوم (ایف پی ایم ایس): اگر، تو۔ تاریخ اور موجودہ نتائج مندرجہ ذیل جدول حقیقی مصنوعات کے مقابلے میں مجموعی پیداوار کے مسئلے پر پیشرفت کا خلاصہ پیش کرتا ہے۔ گیوگی الیکس کے 1/4 اور جوزف سولیموسی کے 1/3 نمائندوں کو حوالہ دینے والے ادب میں سنگ میل کا نتیجہ سمجھا جاتا ہے۔ 2009 کے بعد تمام بہتریاں شکل کی ہیں، اور کونیاگین اور شکریدوف کے دلائل کی اصلاحات کی نمائندگی کرتی ہیں۔ پیچیدہ اعداد ثبوت کی تکنیکیں جن میں صرف زیمیرڈی-ٹراٹر تھیوریم شامل ہے خود بخود پیچیدہ اعداد تک پھیل جاتی ہے، کیونکہ زیمیرڈی-ٹراٹر تھیوریم ٹاتھ کے تھیوریم کے مطابق ہے۔ کونیاگین اور رڈنیف نے پیچیدہ اعداد پر 4/3 کے ایکسپونینٹ کا موازنہ کیا۔ فارم کے متغیرات کے ساتھ نتائج پیچیدہ اعداد پر مماثل نہیں ہوئے ہیں۔ محدود فیلڈز پر جم پروڈکٹ کا مسئلہ خاص طور پر محدود فیلڈز پر اچھی طرح سے مطالعہ کیا جاتا ہے۔ محدود فیلڈ کاکیہ قیاس سے متاثر ہو کر، وولف نے اندازہ لگایا کہ ہر ذیلی سیٹ کے لیے، جہاں ایک (بڑا) پرائم ہے، وہ مطلق مستقل کے لیے ہے۔ یہ قیاس 1990 کی دہائی میں ویگڈرسن نے بھی وضع کیا تھا جو بے ترتیب نکالنے والوں سے متاثر تھا۔ نوٹ کریں کہ جمع پروڈکٹ کا مسئلہ مندرجہ ذیل مثال کی وجہ سے غیر مشروط طور پر محدود فیلڈز میں برقرار نہیں رہ سکتا: مثال: آئیے ایک محدود فیلڈ بنیں اور لے لیں۔ پھر چونکہ اضافہ اور ضرب کے تحت بند کیا جاتا ہے، اور اسی طرح۔ یہ روگیاتی مثال زیر بحث میدان کے کسی بھی ذیلی میدان کو لینے تک پھیلی ہوئی ہے۔ کوالٹی کے لحاظ سے، سم پروڈکٹ کا مسئلہ محدود فیلڈز پر حل کیا گیا ہے: نظریہ (بورگین، کاٹز، تاؤ (2004)): آئیے پرائم ہوں اور کچھ کے لیے ساتھ رہنے دیں۔ پھر کچھ کے لیے ہے۔ بورگین، کاٹز اور تاؤ نے اس نظریہ کو صوابدیدی شعبوں تک بڑھایا۔ غیر رسمی طور پر، مندرجہ ذیل تھیوریم کا کہنا ہے کہ اگر کافی بڑا سیٹ اضافہ یا ضرب کے تحت نہیں بڑھتا ہے، تو یہ زیادہ تر ذیلی فیلڈ کے پھیلاؤ میں موجود ہوتا ہے۔ نظریہ (بورگین، کاٹز، تاؤ (2004)): آئیے ایک محدود فیلڈ کا ذیلی مجموعہ بنیں تاکہ کچھ لوگوں کے لیے اور فرض کریں کہ۔ پھر اس کے ساتھ ایک ذیلی فیلڈ موجود ہے، اور اس کے ساتھ ایک سیٹ موجود ہے۔ وہ تجویز کرتے ہیں کہ مستقل اس سے آزاد ہو سکتا ہے۔ محدود فیلڈ سم پروڈکٹ کے مسئلے کی طرف مقداری نتائج عام طور پر دو زمروں میں آتے ہیں: جب خصوصیت کے حوالے سے چھوٹا ہوتا ہے اور جب خصوصیت کے حوالے سے بڑا ہوتا ہے۔ اس کی وجہ یہ ہے کہ ہر ترتیب میں مختلف قسم کی تکنیکیں استعمال کی جاتی ہیں۔ چھوٹے سیٹ اس نظام میں، خصوصیت کا ایک میدان بننے دیں۔ نوٹ کریں کہ فیلڈ ہمیشہ محدود نہیں ہوتا ہے۔ جب ایسا ہوتا ہے، اور اس کی خصوصیت صفر ہوتی ہے، تو-رکاوٹ کو خارج کر دیا جاتا ہے۔ غیر پرائم آرڈر والے فیلڈز میں،-رکاوٹ کو اس مفروضے سے تبدیل کیا جا سکتا ہے جس میں کسی بھی ذیلی فیلڈ کے ساتھ بہت بڑا چوراہا نہیں ہوتا ہے۔ اس سمت میں بہترین کام لی اور روچے نیوٹن کی وجہ سے ہے جو مندرجہ بالا ٹیبل کے اشارے میں ایک ایکسپوینٹ حاصل کرتے ہیں۔ بڑے سیٹ جب پرائم کے لیے، گریوف کے درج ذیل نتیجہ کی وجہ سے سم پروڈکٹ کا مسئلہ حل سمجھا جاتا ہے: نظریہ (گریوف (2007)): چلو۔ پھر۔ یہ رینج میں بہترین ہے۔ اس نتیجے کو 2011 میں ون کے ذریعے نان پرائم آرڈر کے محدود شعبوں تک بڑھایا گیا تھا۔ متغیرات اور عامیاں آپریٹرز بورگین اور چانگ کے دیگر امتزاج نے سیٹوں کے لیے غیر مشروط ترقی ثابت کی، جب تک کہ کوئی کافی رقم یا مصنوعات پر غور کرے: نظریہ (بورگین، چانگ (2003): چلو۔ پھر موجود ہے تاکہ سب کے لیے، ایک ہے۔ بہت سے کاموں میں، اضافہ اور ضرب کو ایک اظہار میں ملایا جاتا ہے۔ موٹو کے ساتھ اضافہ اور ضرب ایک ساتھ نہیں رہ سکتے، کسی سے توقع کی جاتی ہے کہ کسی سیٹ کے اضافے اور ضرب کے کسی بھی غیر معمولی امتزاج کو ترقی کی ضمانت دینی چاہیے۔ نوٹ کریں کہ محدود ترتیبات میں، یا غیر معمولی ذیلی فیلڈز والے شعبوں میں، اس طرح کے بیان میں مزید رکاوٹوں کی ضرورت ہوتی ہے۔ دلچسپی کے سیٹوں میں شامل ہیں (نتائج کے لیے):-سٹیونز اور وارن دکھاتے ہیں کہ-مرفی، روچے نیوٹن اور شکریدوف دکھاتے ہیں کہ-سٹیونز اور وارن دکھاتے ہیں کہ-سٹیونز اور روڈنوف دکھاتے ہیں کہ خلاصہ سے پاک سیٹ حوالہ جات بھی دیکھیں۔