Quasirandom group
ریاضی میں، کواسی رینڈم گروپ ایک ایسا گروپ ہے جس میں پروڈکٹ سے پاک ایک بڑا ذیلی سیٹ نہیں ہوتا ہے۔ اس طرح کے گروہ قطعی طور پر وہ ہوتے ہیں جن میں چھوٹی غیر معمولی ناقابل تلافی نمائندگی نہیں ہوتی ہے۔ ان گروپوں کے نام گراف تھیوری سے ان کے تعلق سے نکلتے ہیں: کواسیرینڈم گروپ کے کسی بھی ذیلی سیٹ پر دو طرفہ کیلی گراف ہمیشہ دو طرفہ کواسیرینڈم گراف ہوتے ہیں۔ محرک قوسیرینڈم گروپوں کا تصور اس وقت پیدا ہوتا ہے جب گروپوں کے ذیلی سیٹوں پر غور کیا جاتا ہے جن کے لیے ذیلی سیٹ میں کسی بھی دو عناصر کا ذیلی سیٹ میں پروڈکٹ نہیں ہوتا ہے۔ اس طرح کے ذیلی سیٹوں کو پروڈکٹ فری کہا جاتا ہے۔ لاسزلو بابائی اور ویرا سوس نے ایک مستقل کے وجود کے بارے میں پوچھا جس کے لیے آرڈر کے ساتھ ہر محدود گروپ میں کم از کم سائز کے ساتھ پروڈکٹ فری سب سیٹ ہوتا ہے۔ انٹیجرز کے جم فری سیٹوں کے بارے میں پال ایرڈس کا ایک معروف نتیجہ یہ ثابت کرنے کے لیے استعمال کیا جا سکتا ہے کہ ابیلین گروپوں کے لیے کافی ہے، لیکن یہ پتہ چلتا ہے کہ اس طرح کا مستقل غیر ابیلین گروپوں کے لیے موجود نہیں ہے۔ غیر معمولی نچلے اور اوپری دونوں حدود اب آرڈر کے ساتھ گروپ کے سب سے بڑے پروڈکٹ فری سب سیٹ کے سائز کے لیے مشہور ہیں۔ کی ایک نچلی حد کو کافی تعداد میں کوسیٹس کے اتحاد کا ایک بڑا ذیلی سیٹ لے کر ثابت کیا جا سکتا ہے، اور کی ایک اوپری حد کسی بھی پرائم کے لیے پروجیکٹو خصوصی لکیری گروپ پر غور کر کے دی جاتی ہے۔ اوپری حد کو ثابت کرنے کے عمل میں، ٹموتھی گوورز نے پروڈکٹ سے پاک حالت کو سمیٹنے کے لیے ایک قوسیرینڈم گروپ کے تصور کی وضاحت کی اور گراف تھیوری میں قوسیرینڈمنیس سے متعلق مساوات کو ثابت کیا۔ رسمی طور پر، اس بارے میں بات کرنے کا کوئی مطلب نہیں ہے کہ آیا کوئی ایک گروپ کواسرینڈم ہے یا نہیں۔ قوسیرینڈومنیس کی سخت تعریف گروپوں کے سلسلے پر لاگو ہوگی، لیکن پہلے دو طرفہ گراف قوسیرینڈومنیس کی وضاحت کی جانی چاہیے۔ گروہوں کے سلسلے پر غور کرنے کا محرک گرافون کے ساتھ اس کے رابطوں سے پیدا ہوتا ہے، جن کی تعریف ایک خاص معنوں میں گراف کی حدود کے طور پر کی جاتی ہے۔ حقیقی نمبر کو درست کریں دو طرفہ گرافوں کی ایک ترتیب (یہاں تک کہ انٹیجرز کو چھوڑنے کی اجازت ہے جب تک کہ انفنٹی کا رجحان ہو) عمودی، عمودی حصے اور کناروں کے ساتھ اگر مندرجہ ذیل میں سے کوئی بھی مساوی شرائط برقرار ہوں: عمودی حصوں کے ساتھ ہر دو طرفہ گراف کے لیے اور سرایت شدہ اور سرایت شدہ ان کی لیبل شدہ کاپیوں کی تعداد یہاں ہے، فنکشن کو اس پر انحصار کرنے کی اجازت ہے۔ بند، لیبل شدہ واک کی لمبائی 4 کی تعداد شروع میں ہے۔ ذیلی سیٹوں کے کسی بھی جوڑے کے درمیان کناروں کی تعداد اور اس کے لیے ہے، جہاں اس کے ملحقہ میٹرکس کی مشترکہ پڑوسیوں کی تعداد کو ظاہر کرتا ہے اور دیگر تمام آئجین ویلیوز کی زیادہ سے زیادہ شدت ہوتی ہے۔ اس طرح کے گراف کو قوسیرینڈم کہا جاتا ہے کیونکہ ہر شرط اس بات پر زور دیتی ہے کہ جس مقدار پر غور کیا جا رہا ہے وہ تقریبا وہی ہے جس کی توقع کی جائے گی اگر دو طرفہ گراف ایرڈس-رینی بے ترتیب گراف ماڈل کے مطابق تیار کیا گیا تھا۔ یعنی، ہر ممکنہ کنارے کو امکانات کے ساتھ اور آزادانہ طور پر شامل کرنے سے پیدا ہوتا ہے۔ اگرچہ قوسیرینڈمنیس کو صرف گراف کے سلسلے کے لیے بیان کیا جا سکتا ہے، لیکن-قوسیرینڈمنیس کے تصور کو گراف قوسیرینڈمنیس کی مذکورہ بالا تعریفوں میں سے کسی میں بھی غلطی رواداری کی اجازت دے کر ایک مخصوص گراف کے لیے بیان کیا جا سکتا ہے۔ مخصوص ہونے کے لیے، قوسی رینڈمنیس کی کسی بھی مساوی تعریف کو دیکھتے ہوئے، اس اصطلاح کو ایک چھوٹے سے مستقل سے تبدیل کیا جا سکتا ہے، اور اس مخصوص ترمیم شدہ حالت کو پورا کرنے والے کسی بھی گراف کو-قوسی رینڈم کہا جا سکتا ہے۔ یہ پتہ چلتا ہے کہ کسی بھی حالت میں-کواسیرانڈمنیس کسی بھی دوسری حالت میں کسی مطلق مستقل کے لیے-کواسیرانڈمنیس کے برابر ہے۔ گروپ کواسیرانڈمنیس کی وضاحت کے لیے اگلا مرحلہ کیلی گراف ہے۔ بائپارٹائٹ کیلی گراف گراف تھیوریٹک ترتیب میں قوسیرینڈمنیس کو گروپ تھیوریٹک ترتیب میں ترجمہ کرنے کا ایک طریقہ فراہم کرتے ہیں۔ ایک محدود گروپ اور ایک ذیلی سیٹ کو دیکھتے ہوئے، دو طرفہ کیلی گراف دو طرفہ گراف ہے جس میں ورٹیکس سیٹ ہوتے ہیں اور ہر ایک کو عناصر کے ذریعہ لیبل کیا جاتا ہے، جس کے کنارے عمودی کے درمیان ہوتے ہیں جن کا تناسب تعریف کا ایک عنصر ہوتا ہے۔ اوپر بیان کردہ ٹولز کے ساتھ، اب کوئی بھی گروپ کواسرینڈمنیس کی وضاحت کر سکتا ہے۔ (دوبارہ، انٹیجرز کو چھوڑنے کی اجازت ہے) کے ساتھ گروپوں کی ایک ترتیب کواسیرانڈم ہے اگر ہر حقیقی نمبر اور اس کے ساتھ ذیلی سیٹوں کے انتخاب کے لیے، گراف کی ترتیب کواسیرانڈم ہے۔ اگرچہ قوسی رینڈمنیس کی تعریف صرف گروپوں کے سلسلے کے لیے کی جا سکتی ہے، لیکن مخصوص گروپوں کے لیے قوسی رینڈمنیس کے تصور کو مخصوص گرافوں کے لیے قوسی رینڈمنیس کی تعریف کا استعمال کرتے ہوئے گروپوں تک بڑھایا جا سکتا ہے۔ خصوصیات جیسا کہ گوورز نے ثابت کیا ہے، گروپ کواسیرینڈمنیس متعدد مختلف حالات کے مساوی ثابت ہوتی ہے۔ عین مطابق ہونے کے لیے، گروپوں کی ترتیب کو دیکھتے ہوئے، درج ذیل مساوی ہیں: کواسیرینڈم ہے ؛ یعنی، کیلی گراف کے تمام ترتیبات کواسیرینڈم کے ذریعے بیان کیا گیا ہے۔ کی سب سے چھوٹی غیر معمولی نمائندگی کا طول و عرض لامحدود ہے۔ سب سے بڑے پروڈکٹ فری سب سیٹ کا سائز سب سے چھوٹے غیر معمولی حصص کا سائز لامحدود ہے۔ سڈورینڈم گروپوں سے تیار کیے گئے کیلی گراف میں اختلاط کی مضبوط خصوصیات ہوتی ہیں ؛ یعنی، کچھ لوگوں کے لیے جو صفر کی طرف مائل ہوتے ہیں جیسا کہ انفنٹی کی طرف مائل ہوتے ہیں، یہ ایک دو طرفہ گراف ہے۔ (یاد رکھیں کہ گراف عمودی کے ساتھ ایک گراف ہے، ہر ایک ڈگری کے ساتھ، جس کے ملحقہ میٹرکس کی زیادہ سے زیادہ دوسری سب سے بڑی آئجن ویلیو ہوتی ہے) درحقیقت، یہ دکھایا جا سکتا ہے کہ کسی بھی-کواسی رینڈم گروپ کے لیے، حل کی تعداد، کے ساتھ، اور تقریبا اس کے برابر ہے جس کی توقع کی جا سکتی ہے اگر اسے تصادفی طور پر منتخب کیا گیا ہو۔ یعنی، تقریبا برابر۔ یہ نتیجہ ایکسپینڈر مکسنگ لیما کے براہ راست اطلاق سے آتا ہے۔ مثال کے طور پر کواسی رینڈم گروپوں کے کئی قابل ذکر خاندان ہیں۔ ہر معاملے میں، کواسی رینڈمنیس کی خصوصیات کی تصدیق اس کی سب سے چھوٹی غیر معمولی نمائندگی کے طول و عرض کی جانچ کر کے آسانی سے کی جاتی ہے۔ پرائم کے لیے پروجیکٹو اسپیشل لینیر گروپس کواسی رینڈم گروپس کی ایک ترتیب بناتے ہیں، کیونکہ فروبینئس کے ایک کلاسک نتیجہ میں کہا گیا ہے کہ اس کی سب سے چھوٹی غیر معمولی نمائندگی میں کم از کم طول و عرض ہوتا ہے۔ درحقیقت، یہ گروپ وہ گروپ ہیں جن میں گروپ آرڈر کے فنکشن کے طور پر سب سے بڑی کم از کم غیر معمولی نمائندگی ہوتی ہے۔ متبادلاتی گروپ کواسیرانڈم ہیں، کیونکہ اس کی سب سے چھوٹی غیر معمولی نمائندگی کا طول و عرض ہوتا ہے۔ بڑھتی ہوئی ترتیب کے ساتھ غیر چکور سادہ گروپوں کا کوئی بھی سلسلہ کواسیرانڈم ہے، کیونکہ اس کی سب سے چھوٹی غیر معمولی نمائندگی کا طول و عرض کم از کم ہوتا ہے، جہاں گروپ کی ترتیب ہے۔ حوالہ جات گراف تھیوری گروپ تھیوری