ایک قریبی منظر ایک لامحدود گراف کے 'پگھلنے' پوائنٹ کو ظاہر کرتا ہے | کوانٹا میگزین

2008 میں، ریاضی دان Oded Schramm سیئٹل سے تقریباً 50 میل مشرق میں کاسکیڈ پہاڑوں میں پیدل سفر کے ایک حادثے میں مر گیا۔ اگرچہ وہ صرف 46 سال کا تھا، اس نے ریاضی کے بالکل نئے شعبے بنا لیے تھے۔

"وہ ایک لاجواب ریاضی دان تھا،" کہا ایٹائی بنجمینی, Weizmann انسٹی ٹیوٹ آف سائنس میں ایک ریاضی دان اور Schramm کے دوست اور معاون۔ "انتہائی تخلیقی، انتہائی خوبصورت، انتہائی اصل۔"

اس کے پوچھے گئے سوالات اب بھی امکانی تھیوری اور شماریاتی طبیعیات کی سرحدوں کو آگے بڑھا رہے ہیں۔ ان میں سے بہت سے سوالات ریاضیاتی ڈھانچے سے متعلق ہیں جن میں ایک مرحلے کی منتقلی ہوتی ہے - اچانک میکروسکوپک تبدیلی، جیسے برف کا پانی میں پگھلنا۔ جس طرح مختلف مادوں کے مختلف پگھلنے والے مقامات ہوتے ہیں، اسی طرح ریاضی کے ڈھانچے کے مرحلے کی منتقلی بھی مختلف ہوتی ہے۔

شرام نے قیاس کیا کہ پرکولیشن نامی عمل میں مرحلے کی منتقلی کا اندازہ بہت سے اہم ریاضیاتی ڈھانچے کے لیے نظام کے صرف قریبی نقطہ نظر سے لگایا جا سکتا ہے - جسے مقامی تناظر کہا جاتا ہے۔ پورے راستے کو زوم کرنے اور پوری چیز کو دیکھنے سے حساب میں کوئی خاص تبدیلی نہیں آئے گی۔ پچھلے 15 سالوں میں، ریاضی دانوں نے قیاس کے چھوٹے چھوٹے ٹکڑوں کو دور کر دیا ہے، لیکن اب تک، وہ اسے مکمل طور پر حل کرنے میں کامیاب نہیں ہو سکے ہیں۔

ایک اکتوبر میں شائع شدہ پری پرنٹ, ٹام ہچ کرافٹ کیلیفورنیا انسٹی ٹیوٹ آف ٹیکنالوجی اور اس کے ڈاکٹریٹ کے طالب علم فلپ ایزو Schramm کے مقامی قیاس کو ثابت کیا۔ ان کا ثبوت امکانی نظریہ اور ریاضی کے دیگر شعبوں کے بڑے نظریات پر انحصار کرتا ہے، جنہیں انہوں نے ایک ہوشیار طریقے سے جوڑ دیا۔

"یہ ایک قابل ذکر کاغذ ہے. یہ طویل کام کا مجموعہ ہے،" بنجمینی نے کہا۔

لامحدود کلسٹرز

لفظ "پرکولیشن" اصل میں ایک غیر محفوظ ذریعہ سے سیال کی نقل و حرکت کا حوالہ دیتا ہے، جیسے کافی کے میدانوں سے بہتا ہوا پانی یا چٹان میں شگافوں سے تیل کا بہنا۔

1957 میں، ریاضی دانوں سائمن رالف براڈبینٹ اور جان مائیکل ہیمرسلے نے اس جسمانی عمل کا ایک ریاضیاتی ماڈل تیار کیا۔ اس کے بعد کی دہائیوں میں، یہ ماڈل اپنے طور پر مطالعہ کا موضوع بن گیا ہے۔ ریاضی دان پرکولیشن کا مطالعہ کرتے ہیں کیونکہ یہ ایک اہم توازن کو متاثر کرتا ہے: سیٹ اپ آسان ہے، لیکن یہ پیچیدہ اور حیران کن خصوصیات کو ظاہر کرتا ہے۔

"یہ ریاضی دانوں کے لیے ایک روایتی ماڈل کی طرح ہے،" ہچ کرافٹ نے کہا۔ "آپ چیزوں کے بارے میں بصری طور پر سوچ سکتے ہیں۔ اس کے ساتھ کام کرنا واقعی اچھا لگتا ہے۔"

ٹکرانا ایک گراف کے ساتھ شروع ہوتا ہے، جو عمودی خطوط (پوائنٹس) کا مجموعہ ہے جو کناروں (لائنوں) کے ذریعے جڑا جا سکتا ہے۔ سب سے آسان مثالوں میں سے ایک مربع گرڈ ہے، جس کے عمودی حصے چوکوں اور کناروں کے کونوں کو بناتے ہیں جو ان میں سے کچھ کو جوڑتے ہیں۔

اپنی موت سے کچھ دیر پہلے، شرام نے قیاس کیا کہ گریمیٹ اور مارسٹرینڈ کے نظریے کو عام کیا جا سکتا ہے۔ اس نے سوچا کہ پرکولیشن تھریشولڈ کا تعین مکمل طور پر قریبی اپ، یا "مائکروسکوپک" نقطہ نظر سے ہوتا ہے جو گرافوں کے ایک بڑے طبقے کے لیے ہوتا ہے جسے عبوری گراف کہا جاتا ہے۔

2009 میں، بنیامینی، آصف نچمیاس اور یوول پیریز ثابت ہوا Schramm کا مقامی قیاس، جیسا کہ اب یہ جانا جاتا ہے، ایک مخصوص قسم کے عبوری گراف کے لیے جو درخت سے مشابہت رکھتا ہے۔ تاہم، Schramm، نے فرض کیا تھا کہ یہ تمام عبوری گرافس کے لیے رکھے گا (ایک جہتی گراف کے لیے استثناء کے ساتھ)۔

ایک عبوری گراف میں، تمام عمودی شکلیں ایک جیسی نظر آتی ہیں۔ دو جہتی گرڈ ایک مثال ہے۔ اگر آپ کوئی بھی دو چوٹیوں کو چنتے ہیں، تو آپ ہمیشہ ایک ہم آہنگی تلاش کر سکتے ہیں جو ایک چوٹی کو دوسرے کی طرف لے جاتی ہے۔

یہ تعلق کسی بھی عبوری گراف کے لیے رکھتا ہے۔ ان ہم آہنگی کی وجہ سے، اگر آپ زوم ان کریں اور ٹرانزیٹو گراف کے کسی بھی دو برابر سائز کے پیچ کو دیکھیں تو وہ ایک جیسے نظر آئیں گے۔ اس وجہ سے، Schramm کا خیال تھا کہ قریبی نقطہ نظر ریاضی دانوں کو تمام عبوری گرافوں کے لیے پرکولیشن کی حد کا حساب لگانے کے لیے کافی تھا۔

عبوری گراف بہت سی شکلیں اور شکلیں لے سکتے ہیں۔ وہ ایک سادہ گرڈ ہو سکتا ہے، جو مربع، مثلث، مسدس یا کسی دوسری شکل سے بنا ہوا ہے۔ یا وہ ایک "3-باقاعدہ درخت" کی طرح ایک زیادہ پیچیدہ چیز تشکیل دے سکتے ہیں، جہاں ایک مرکزی نقطہ تین عمودی حصوں سے جڑتا ہے، اور ہر چوٹی پھر شاخیں بنا کر دو نئے اشتھاراتی لامحدود تخلیق کرتی ہیں، جن کے پہلے چند مراحل یہاں دیکھے گئے ہیں:

مختلف قسم کے عبوری گرافس نے شریم کے مقامی قیاس کو ثابت کرنے میں دشواری کا باعث بنا۔ Schramm کے قیاس اور Easo اور Hutchcroft کے ثبوت کے درمیان 15 سالوں میں، ریاضی دانوں کے مختلف گروہوں نے گراف کی مخصوص قسموں کے لیے قیاس کو ثابت کیا، لیکن ان کے خیالات کبھی بھی عام کیس تک نہیں بڑھے۔

ہچ کرافٹ نے کہا کہ "تمام ممکنہ جیومیٹریوں کی جگہ بہت وسیع ہے، اور وہاں ہمیشہ عجیب و غریب چیزیں چھپی رہتی ہیں۔"

لینس کو چوڑا کرنا

Easo اور Hutchcroft شروع میں Schramm کے مقامی قیاس کے حل کی تلاش میں نہیں تھے، جو کہ لامحدود گرافس پر لاگو ہوتا ہے۔ وہ اس کے بجائے محدود گرافس پر ٹکرانے کا مطالعہ کر رہے تھے۔ لیکن ان کے پاس ایک خیال تھا جس نے اچانک ان کی توجہ قیاس کی طرف مبذول کر دی۔

Easo نے کہا، "ہم اس نئے آلے کے ساتھ آئے ہیں، اور ہم نے سوچا، اوہ، یہ اس قسم کی چیز کی طرح لگتا ہے جو محلے پر حملہ کرنے میں مددگار ہو سکتی ہے،" Easo نے کہا۔

قیاس کو ثابت کرنے کے لیے، انہیں یہ ظاہر کرنے کی ضرورت تھی کہ خوردبین نقطہ نظر ٹکرانے کی حد کا ایک درست تصویر پیش کرتا ہے۔ جب آپ گراف کا صرف ایک حصہ دیکھتے ہیں اور ایک بڑے جڑے ہوئے کلسٹر کا مشاہدہ کرتے ہیں، تو آپ یہ فرض کر سکتے ہیں کہ گراف میں ایک لامحدود کلسٹر ہے اور اس لیے یہ ٹکرانے کی حد سے اوپر ہے۔ Easo اور Hutchcroft اسے ثابت کرنے کے لیے نکلے ہیں۔

انہوں نے ایک ایسی تکنیک پر انحصار کیا جس کے بارے میں سوچا جا سکتا ہے کہ "عینک کو چوڑا کرنا"۔ ایک ہی چوٹی سے شروع کریں۔ پھر ان تمام چوٹیوں کو دیکھنے کے لیے زوم آؤٹ کریں جو اصل گراف پر صرف ایک کنارے کے فاصلے پر ہیں۔ مربع گرڈ پر، اب آپ کل پانچ چوٹیوں کو دیکھ سکیں گے۔ دو کناروں کے فاصلے کے اندر تمام چوٹیوں کو دیکھنے کے لیے لینس کو دوبارہ چوڑا کریں، اور پھر تین کناروں، چار کناروں، وغیرہ کا فاصلہ۔

Easo اور Hutchcroft نے ڈائل سیٹ کیا جو اس بات کا تعین کرتا ہے کہ جہاں انہوں نے ایک بڑا کلسٹر دیکھا اس کے قریب کتنے لنکس ہیں۔ اس کے بعد انہوں نے عینک کو چوڑا کیا، اپنے بڑے جھرمٹ میں زیادہ سے زیادہ کناروں کو جمع ہوتے دیکھ کر۔ جیسا کہ انہوں نے ایسا کیا، انہیں اس امکان کو بڑھانا پڑا کہ لنکس موجود ہوں گے، جس سے یہ ظاہر کرنا آسان ہو جاتا ہے کہ گراف میں ایک بڑا منسلک جزو ہے۔ یہ ایک نازک توازن عمل ہے۔ انہیں دیکھنے کے میدان کو تیزی سے وسیع کرنے اور ڈائل کی پوزیشن کو ڈرامائی طور پر تبدیل کیے بغیر مکمل لامحدود گراف کو ظاہر کرنے کے لیے کافی آہستہ آہستہ لنکس شامل کرنے کی ضرورت تھی۔

وہ یہ دکھانے کے قابل تھے کہ بڑے جھرمٹ چھوٹے سے زیادہ تیزی سے بڑھتے ہیں، تاکہ، جیسا کہ Easo نے کہا، "آپ کا جھرمٹ تیزی سے اور تیزی سے بڑھتا ہے جیسا کہ یہ بڑا اور بڑا ہوتا جاتا ہے، بالکل اسی طرح جب آپ برف کا گولہ چلا رہے ہوتے ہیں۔"

مربع گرڈ کے لیے، چوٹی کی گنتی نسبتاً آہستہ بڑھتی ہے۔ یہ آپ کے لینس کے مربع کی چوڑائی تقریباً ہے۔ 10 قدموں کے بعد، آپ کو لگ بھگ 100 چوٹییں ملیں گی۔ لیکن ایک 3-باقاعدہ درخت تیزی سے بڑھتا ہے - تقریباً 2 آپ کے لینس کی چوڑائی کی طاقت تک بڑھتا ہے۔ 10 قدموں کے بعد، آپ کو تقریباً 1,024 عمودی شکلیں نظر آئیں گی۔ نیچے دی گئی مثال سے پتہ چلتا ہے کہ کس طرح 3-باقاعدہ درخت صرف سات قدموں کے بعد بہت بڑا ہوتا ہے، حالانکہ مربع گرڈ میں پہلے زیادہ چوٹی ہوتی ہے۔ عام طور پر، گراف میں مختلف پیمانے پر ترقی کی شرح مختلف ہو سکتی ہے - وہ تیزی سے شروع ہو سکتے ہیں، اور پھر سست ہو سکتے ہیں۔

2018 میں واپس، ہچ کرافٹ اسی طرح کا خیال استعمال کیا 3-باقاعدہ درخت کی طرح تیزی سے بڑھتے ہوئے گرافس کے لیے مقامی قیاس کو ثابت کرنے کے لیے۔ لیکن اس نے اسکوائر گرڈ جیسے سست نمو والے گرافس، یا درمیانی رفتار سے بڑھنے والے گرافس کے لیے کام نہیں کیا، جو نہ تو تیز رفتار ترقی کے لیے ریاضیاتی معیار پر پورا اترتا ہے اور نہ ہی سست ترقی کے لیے۔

ہچ کرافٹ نے کہا ، "یہ وہ جگہ ہے جہاں چیزیں تین سالوں کی طرح واقعی مایوس کن ہوتی ہیں۔

ساخت بمقابلہ توسیع

گرافس کے لیے جو ترقی کی شرح کو مختلف پیمانے پر ملاتے ہیں، آپ کو مختلف تکنیکوں کا استعمال کرنا ہوگا۔

ایک بہت مددگار حقیقت یہ ہے کہ، جیسا کہ Easo نے وضاحت کی، "اگر کوئی گراف کسی پیمانے پر سست ترقی کرتا نظر آتا ہے، تو وہ پھنس جاتا ہے۔" یہ بڑے پیمانے پر آہستہ آہستہ بڑھتا رہے گا۔ چونکہ سست نمو والے گرافس میں ریاضی کی ایک شاخ جس کا تعین گروپ تھیوری کے ذریعہ کیا جاتا ہے، یہ بھی معلوم تھا کہ اگر آپ کافی حد تک زوم آؤٹ کرتے ہیں، تو سست نمو والے گرافس جیومیٹری کو ظاہر کرتے ہیں جو کہ ریاضی کے لحاظ سے موزوں ہے۔

2021 میں، پیرس میں سوربون یونیورسٹی کے سیبسٹین مارٹنیو، ڈینیئل کونٹریاس کے ساتھ کام کر رہے ہیں اور ونسنٹ ٹیشن ETH زیورخ کے، اس پراپرٹی کو استعمال کرنے کے قابل تھا۔ Schramm کے مقامی قیاس کو ثابت کریں۔ گرافس کے لیے جو آخر کار آہستہ آہستہ بڑھتے ہیں۔

اس مقام پر، ریاضی دانوں کے دو گروہوں نے کامیابی سے مختلف سمتوں سے قیاس آرائیوں سے نمٹا: تیز نمو اور سست نمو۔ لیکن اس نے بڑے فرق کو چھوڑ دیا۔ ایک تو، ایک درمیانی ترقی کا زمرہ ہے جس کا احاطہ Easo اور Hutchcroft کی تکنیک یا Contreras، Martineau اور Tassion کے ثبوت کے ذریعے نہیں کیا گیا تھا۔ ایک اور مسئلہ یہ تھا کہ دلائل اب بھی بدلتے ہوئے شرح نمو کے ساتھ گراف پر لاگو نہیں ہوتے تھے - صرف وہی جو تیز یا سست رہے۔ Contreras، Martineau اور Tassion کے استدلال کے لیے صوابدیدی گراف پر لاگو ہونے کے لیے، یہ کافی نہیں تھا کہ جب آپ زوم آؤٹ کرتے ہیں تو جیومیٹری آخرکار اچھی لگتی ہے، Easo نے وضاحت کی: "ہمیں موجودہ پیمانے کے قریب، اب ڈھیٹ نظر آنے کی ضرورت ہے۔"

کہیں کا مڈل

درمیانی ترقی کے عبوری گراف بہت پراسرار ہیں۔ ریاضی دانوں کو کبھی بھی ایسے عبوری گراف کی مثال نہیں ملی جس کی نمو اس حد میں آتی ہو۔ یہ ممکن ہے کہ وہ موجود نہ ہوں۔ لیکن ریاضی دانوں نے یہ ثابت نہیں کیا کہ ان کا کوئی وجود نہیں ہے، اس لیے Schramm کے مقامی قیاس کے کسی بھی مکمل ثبوت کو ان پر توجہ دینا چاہیے۔ چیلنج میں اضافہ کرتے ہوئے، Easo اور Hutchcroft کو ایسے گرافس کو ایڈریس کرنے کی ضرورت ہے جن میں صرف مختصر طور پر ایک خاص لمبائی کے پیمانے پر درمیانی نمو ہو سکتی ہے، چاہے وہ تیز یا آہستہ بڑھیں جب آپ زوم ان یا آؤٹ کرتے ہیں۔

Easo اور Hutchcroft نے پچھلے سال کا زیادہ تر حصہ اپنے نتائج کو ان گرافس پر لاگو کرنے کے لیے بڑھایا جو پہلے کے کسی بھی طریقے میں شامل نہیں تھے۔

سب سے پہلے، انہوں نے 2018 کی تکنیک میں ترمیم کی جسے ہچ کرافٹ نے تیزی سے بڑھتے ہوئے گرافس پر کام کرنے کے لیے لاگو کیا تھا جو مختلف پیمانے پر ترقی کی سطح کو تبدیل کرتے ہیں۔ اس کے بعد انہوں نے سست نمو کے معاملے سے نمٹا ایک 27 صفحات کا کاغذ انہوں نے اگست میں اشتراک کیا جو Contreras، Martineau، اور Tassion پر کام پر پھیل گیا۔ آخر کار، اپنے اکتوبر کے پری پرنٹ میں، انہوں نے بے ترتیب چہل قدمی کے نظریہ کا استعمال کرتے ہوئے ایک اور دلیل تیار کی — لائنیں جو خلا میں بے ترتیب طور پر گھومتی ہیں — درمیانی ترقی کے معاملے کو سنبھالنے کے لیے۔ ٹرائیکوٹومی مکمل ہونے کے بعد، انہوں نے شرام کے مقامی قیاس کو ثابت کر دیا تھا۔

ہچ کرافٹ نے کہا کہ "ہمیں وہ سب کچھ پھینکنا پڑا جو ہم جانتے تھے۔

یہ حل ریاضی دانوں کو ایک بہتر بصیرت فراہم کرتا ہے کہ پرکولیشن تھریشولڈ کے اوپر کیا ہوتا ہے، جہاں لامحدود کلسٹر کا امکان 100٪ ہے، اور اس کے نیچے، جہاں موقع 0٪ ہے۔ لیکن ریاضی دان اب بھی اس بات سے حیران ہیں کہ تین جہتی گرڈ سمیت زیادہ تر گرافوں کی دہلیز پر بالکل کیا ہوتا ہے۔ "یہ پرکولیشن تھیوری میں شاید سب سے مشہور، سب سے بنیادی کھلا سوال ہے،" کہا رسل لیونز انڈیانا یونیورسٹی کے.

دو جہتی گرڈ ان چند صورتوں میں سے ایک ہے جہاں ریاضی دانوں نے ثابت کیا ہے کہ بالکل دہلیز پر کیا ہوتا ہے: لامحدود کلسٹرز نہیں بنتے۔ اور جب Grimmett اور Marstrand نے بڑے سلیبوں کے لیے مقامی قیاس کا ایک ورژن ثابت کیا تو، Grimmett اور collaborators نے دکھایا کہ اگر آپ 3D گرڈ کو آدھے افقی طور پر کاٹتے ہیں، ایک فرش بناتے ہیں، اور ڈائل کو بالکل پرکولیشن تھریشولڈ پر ٹیون کرتے ہیں، تو کوئی لامحدود کلسٹر ظاہر نہیں ہوتا۔ ان کا نتیجہ اشارہ کرتا ہے کہ مکمل تین جہتی گرڈ، اس کے دو جہتی ہم منصب کی طرح، ٹکرانے کی دہلیز پر لامحدود کلسٹر نہیں ہوسکتا ہے۔

1996 میں، بنیامینی اور شرام قیاس کہ دہلیز پر لامحدود کلسٹر تلاش کرنے کا موقع تمام عبوری گرافس کے لیے صفر ہے — بالکل اسی طرح جیسے یہ 2D گرڈ کے لیے ہے یا آدھے حصے میں کٹے ہوئے 3D گرڈ کے لیے۔ اب جب کہ مقامی قیاس آرائیاں ہو چکی ہیں، منتقلی کے مقام پر کیا ہوتا ہے اس کی سمجھ تھوڑی قریب آ سکتی ہے۔

اصلاح: دسمبر 18، 2023
3-ریگولر گراف پر شروع ہونے والے نوڈ کے n لنکس کے اندر نوڈس کی تعداد تقریباً 2 تک بڑھتی ہے۔ⁿ، 3 نہیںⁿ جیسا کہ اس مضمون میں اصل میں کہا گیا ہے۔ مضمون میں تصحیح کر دی گئی ہے۔

Quanta ہمارے سامعین کی بہتر خدمت کے لیے سروے کا ایک سلسلہ کر رہا ہے۔ ہماری لے لو ریاضی کے ریڈر سروے اور آپ کو مفت جیتنے کے لیے داخل کیا جائے گا۔ Quanta مرچ۔