Hypergraph regularity method
ریاضی میں، ہائپر گراف باقاعدگی کا طریقہ انتہائی گراف تھیوری میں ایک طاقتور ٹول ہے جو ہائپر گراف باقاعدگی لیما اور متعلقہ گنتی لیما کے مشترکہ اطلاق سے مراد ہے۔ یہ گراف باقاعدگی کے طریقہ کار کی عمومی شکل ہے، جس سے مراد زیمیرڈی کی باقاعدگی اور گنتی لیما کا استعمال ہے۔ بہت غیر رسمی طور پر، ہائپر گراف باقاعدگی لیما کسی بھی دیئے گئے یکساں ہائپر گراف کو بے ترتیب جیسی چیز میں بند حصوں کے ساتھ (مناسب حد بندی اور بے ترتیب تصورات کے ساتھ) تحلیل کرتا ہے جس کے ساتھ عام طور پر کام کرنا آسان ہوتا ہے۔ دوسری طرف، ہائپر گراف کاؤنٹنگ لیما بے ترتیب جیسے حصوں کے کچھ مجموعوں میں دی گئی آئسومورفزم کلاس کے ہائپر گراف کی تعداد کا تخمینہ لگاتا ہے۔ یہ Szemerédi کی باقاعدگی لیما کی توسیع ہے جو کسی بھی گراف کو باؤنڈڈ نمبر حصوں میں تقسیم کرتی ہے تاکہ حصوں کے درمیان کنارے تقریبا بے ترتیب انداز میں برتاؤ کریں۔ اسی طرح، ہائپر گراف کاؤنٹنگ لیما گراف کاؤنٹنگ لیما کی عمومی شکل ہے جو ایک بڑے گراف کے ذیلی گراف کے طور پر ایک مقررہ گراف کی نقلوں کی تعداد کا تخمینہ لگاتا ہے۔ اس طریقہ کار کی کئی الگ الگ تشکیلات ہیں، جن میں سے سبھی ہائپر گراف ہٹانے والے لیما اور متعدد دیگر طاقتور نتائج کا اشارہ کرتی ہیں، جیسے کہ زیمیرڈی کا نظریہ، نیز اس کی کچھ کثیر جہتی توسیعات۔ مندرجہ ذیل فارمولیشنز وی روڈل، بی ناگلے، جے سکوکن، ایم شیچٹ، اور وائی کوہاکاوا کی وجہ سے ہیں، متبادل ورژن کے لیے تاؤ (2006)، اور گوورز (2007) دیکھیں۔ تعریفیں ہائپر گراف کی باقاعدگی اور لیما کی گنتی کو باضابطہ طور پر بیان کرنے کے لیے، ہمیں متعدد تکنیکی اصطلاحات کی وضاحت کرنے کی ضرورت ہے تاکہ فرضی بے ترتیب (بے ترتیب-مشابہت) اور حدود کے مناسب تصورات کو باقاعدہ بنایا جا سکے، ساتھ ہی بے ترتیب جیسے بلاکس اور پارٹیشنز کو بیان کیا جا سکے۔ نوٹیشن عمودی پر ایک یکساں کلک کی نشاندہی کرتا ہے۔ ورٹیکس پارٹیشن پر ایک-پارٹیٹ-گراف ہے۔ تمام-عنصر ورٹیکس سیٹوں کا خاندان ہے جو کلک میں پھیلا ہوا ہے۔ خاص طور پر، ایک مکمل پارٹائٹ گراف ہے۔ مندرجہ ذیل رشتہ دار کثافت کے ایک اہم تصور کی وضاحت کرتا ہے، جو ہائپر گراف میں موجود کناروں کے ذریعے پھیلے ہوئے کناروں کے حصے کو تقریبا بیان کرتا ہے۔ مثال کے طور پر، جب مقدار ذیلی ہائپر گراف میں 2 کنارے والے مثلث کے حصے کے برابر ہوتی ہے جو 3 کنارے والے ہوتے ہیں۔ تعریف [رشتہ دار کثافت]۔ اس کے لیے، کچھ کلاسیں ٹھیک کریں۔ فرض کریں کہ یہ ایک عدد ہے۔ آئیے انڈیوسڈ-پارٹیٹ گراف کا سب ہائپر گراف بنیں۔ رشتہ دار کثافت کی وضاحت کریں۔ اس کے بعد سڈورینڈومنیس کا مناسب تصور کیا ہے جو باقاعدگی کا طریقہ استعمال کرے گا۔ غیر رسمی طور پر، باقاعدگی کے اس تصور کے مطابق،-کنارے () کا-کنارے () پر کچھ کنٹرول ہوتا ہے۔ مزید واضح طور پر، یہ ایک ایسی ترتیب کی وضاحت کرتا ہے جہاں بڑے سب ہائپر گراف میں کناروں کی کثافت تقریبا وہی ہوتی ہے جس کی توقع صرف رشتہ دار کثافت کی بنیاد پر کی جاتی ہے۔ رسمی طور پر، تعریف [()-باقاعدگی]۔ فرض کریں کہ مثبت حقیقی اعداد ہیں اور یہ ایک عدد عدد ہے۔ کلاسوں کے کسی بھی انتخاب اور اطمینان بخش سب ہائپر گراف کے کسی بھی مجموعہ کے حوالے سے () باقاعدہ ہے۔ واضح طور پر، درج ذیل سڈورینڈم بلاکس کی وضاحت کرتا ہے جس میں ہائپر گراف باقاعدگی لیما کسی بھی بڑے کافی ہائپر گراف کو ختم کرتا ہے۔ Szemerédi باقاعدگی میں، 2 کنارے بمقابلہ 1 کنارے (عمودی) کو باقاعدہ بنایا جاتا ہے۔ اس عمومی تصور میں،-کنارے کو باقاعدہ کیا جاتا ہے بمقابلہ-کنارے سب کے لیے۔ مزید واضح طور پر، یہ باقاعدہ ہائپر گراف کے تصور کی وضاحت کرتا ہے جسے کمپلیکس کہا جاتا ہے، جس میں ایج کا وجود تمام بنیادی کناروں کے وجود کے ساتھ ساتھ ان کی نسبتا باقاعدگی کو بھی ظاہر کرتا ہے۔ مثال کے طور پر، اگر 3 کنارے ہیں تو،، اور کمپلیکس میں 2 کنارے ہیں۔ مزید برآں، 2 کناروں کے ذریعے بنائے گئے تمام ممکنہ مثلثوں پر 3 کناروں کی کثافت subhypergraphs.Definition [-ریگولر-کمپلیکس] کے ہر مجموعہ میں تقریبا یکساں ہے۔ کمپلیکس پارٹائٹ گراف کا ایک ایسا نظام ہے جو اطمینان بخش ہے۔ مثبت حقیقی اعداد کے ویکٹر، اور ایک عدد کو دیکھتے ہوئے، ہم کہتے ہیں کہ-پیچیدہ-باقاعدہ ہے اگر ہر ایک کے لیے، کثافت کے ساتھ-باقاعدہ ہے۔ ہر ایک کے لیے، ہے ()-کے حوالے سے باقاعدہ۔ مندرجہ ذیل مساوی تقسیم کو بیان کرتا ہے جسے ہائپر گراف باقاعدگی لیما متاثر کرے گا۔ تقسیم کا ایک مساوی خاندان 1-کنارے (عمودی)، 2-کنارے (جوڑے)، 3-کنارے (ٹرپل) وغیرہ کی تقسیم کا ایک سلسلہ ہے۔ یہ Szemerédi کی باقاعدگی لیما کے ذریعہ حاصل کردہ تقسیم سے ایک اہم فرق ہے، جہاں صرف عمودی حصے تقسیم کیے جا رہے ہیں۔ درحقیقت، گوورز نے یہ مظاہرہ کیا کہ صرف ورٹیکس پارٹیشن ہی ہائپر گراف کاؤنٹنگ لیما کو ظاہر کرنے کے لیے باقاعدگی کا کافی مضبوط تصور نہیں دے سکتا۔ تعریف [-مساوی تقسیم]۔ فرض کریں کہ ایک حقیقی عدد ہو، ایک عدد ہو، اور مثبت حقیقی کے ویکٹر ہوں۔ آئیے مثبت انٹیجرز کا ویکٹر بنیں اور ایک-عنصر ورٹیکس سیٹ بنیں۔ ہم کہتے ہیں کہ پارٹیشنوں کا ایک خاندان-مساوی ہے اگر یہ مندرجہ ذیل کو مطمئن کرتا ہے: کی مساوی ورٹیکس پارٹیشن ہے۔ یہ ہے۔ پارٹیشن تاکہ اگر اور پھر زیادہ تر حصوں میں تقسیم کیا جائے، یہ سب ممبر ہیں۔ سب کے لیے لیکن زیادہ سے زیادہ-tuples میں منفرد-ریگولر-کمپلیکس ہوتا ہے جس میں اراکین کے طور پر مختلف پارٹیشن کلاسز ہوتی ہیں۔ آخر میں، مندرجہ ذیل وضاحت کرتا ہے کہ پارٹیشن کے حوالے سے-یونیفارم ہائپر گراف کے لیے ریگولر ہونے کا کیا مطلب ہے۔ خاص طور پر، یہ بنیادی تعریف ہے جو ہائپر گراف ریگولرٹی لیما bellow.Definition [پارٹیشن کے حوالے سے ریگولرٹی] کی آؤٹ پٹ کو بیان کرتی ہے۔ ہم کہتے ہیں کہ تقسیم کے خاندان کے حوالے سے ایک-گراف باقاعدہ ہے اگر سب کے پاس لیکن زیادہ تر کناروں پر وہ خاصیت ہے جو اور اگر منفرد ہے-پیچیدہ جس کے لیے، تو اس کے حوالے سے باقاعدہ ہے۔ بیانات ہائپر گراف باقاعدگی لیما تمام مثبت حقیقی، اور افعال کے لیے، موجود ہے اور اس طرح کہ مندرجہ ذیل برقرار رہتا ہے۔ عمودی پر کسی بھی یکساں ہائپر گراف کے لیے، پارٹیشنوں کا ایک خاندان اور ایک ویکٹر موجود ہوتا ہے تاکہ، سب کے لیے اور کہاں کے لیے، درج ذیل برقرار رہے۔ تقسیم کا ایک مساوی خاندان ہے اور ہر ایک کے لیے۔ کے حوالے سے باقاعدہ ہے۔ ہائپر گراف کاؤنٹنگ لیما تمام انٹیجرز کے لیے درج ذیل ہے: اور انٹیجرز ہیں اور تاکہ، کے ساتھ، اور، اگر ورٹیکس پارٹیشن کے ساتھ ایک-ریگولر کمپلیکس ہے اور پھر۔ ایپلی کیشنز بنیادی ایپلی کیشن جس کے ذریعے زیادہ تر دوسرے پیروی کرتے ہیں وہ ہائپر گراف ہٹانے والا لیما ہے، جس میں تقریبا کہا گیا ہے کہ مقررہ اور بڑے یکساں ہائپر گراف دیئے گئے ہیں، اگر ان کی چند کاپیاں ہوں، تو کوئی بھی ان کی تمام کاپیوں کو ختم کرنے کے لیے کچھ ہائپر ایجز کو حذف کر سکتا ہے۔ اسے مزید رسمی طور پر بیان کرنے کے لیے، ہائپر گراف ہٹانے کا لیما سب کے لیے موجود ہے اور اس طرح مندرجہ ذیل برقرار رہتا ہے۔ فرض کریں کہ عمودی پر ایک یکساں ہائپر گراف ہے اور عمودی پر ہے۔ اگر اس کی زیادہ تر کاپیاں موجود ہیں، تو کوئی بھی اسے آزاد بنانے کے لیے ہائپر ایجز کو حذف کر سکتا ہے۔ گراف کے باقاعدگی کے طریقہ کار کے اصل محرکات میں سے ایک زیمیرڈی کے نظریہ کو ثابت کرنا تھا، جس میں کہا گیا ہے کہ ہر گھنے ذیلی سیٹ میں صوابدیدی لمبائی کی ریاضی کی ترقی ہوتی ہے۔ در حقیقت، مثلث ہٹانے والے لیما کے نسبتا سادہ اطلاق سے، یہ ثابت کیا جا سکتا ہے کہ مثلث کے ہر گھنے ذیلی سیٹ میں لمبائی 3 کی ریاضی کی ترقی ہوتی ہے۔ ہائپر گراف باقاعدگی کا طریقہ اور ہائپر گراف ہٹانے کا لیما زیمیرڈی کے نظریات کے کثافت ورژن کے اعلی جہتی اور رنگ اینالاگس کو ثابت کر سکتا ہے، جو اصل میں فرسٹن برگ اور کاٹز نیلسن نے ثابت کیا تھا۔ درحقیقت، یہ نقطہ نظر نظریات کے لیے پہلی مقداری حدود پیدا کرتا ہے۔ یہ تھیوریم تقریبا اس بات کا اشارہ کرتا ہے کہ کے کسی بھی گھنے ذیلی سیٹ میں کے کسی بھی محدود پیٹرن پر مشتمل ہے۔ جب اور نمونہ کچھ لمبائی کی ریاضی کی ترقی ہے تو یہ زیمیرڈی کے نظریہ کے مساوی ہے۔ فرسٹن برگ اور کاٹز نیلسن تھیوریم کو ایک محدود ذیلی سیٹ ہونے دیں اور دیا جائے۔ پھر ایک محدود ذیلی سیٹ موجود ہے جس میں ہر ایک کے ساتھ ایک ہوموتھیٹک کاپی ہوتی ہے۔ (یعنی۔ شکل کا مجموعہ، کچھ کے لیے اور) اس کے علاوہ، اگر کچھ کے لیے، تو ایسی چیز موجود ہے جس میں یہ خاصیت سب کے لیے ہے۔ ایک اور ممکنہ عمومی شکل جسے ہٹانے والے لیما سے ثابت کیا جا سکتا ہے وہ ہے جب طول و عرض کو بڑھنے دیا جاتا ہے۔ ٹینگن، ٹوکوشیج، روڈیل، اور شیچ تھیوریم ایک محدود رنگ ہونے دیں۔ ہر ایک کے لیے، ایسا موجود ہے کہ، کسی بھی ذیلی سیٹ کے ساتھ (بائیں-ماڈیول کے طور پر) کی آئسومورفک کاپی کا ایک کوزیٹ ہوتا ہے۔ دوسرے لفظوں میں، کچھ ایسے ہیں جو، جہاں، ایک انجکشن ہے۔ حوالہ جات گراف تھیوری