ریاضیاتپیش‌چاپنظریه۴ دقیقه مطالعه

شبکه‌های تصادفی در چگالی‌ای ثابت دیگر رنگ‌پذیر نیستند

یک گراف بردارید — نقطه‌هایی که با پیوندها به هم وصل‌اند — و جعبه‌ای از رنگ‌ها. یک رنگ‌آمیزی سره (proper colouring) با q رنگ به هر نقطه یکی از q رنگ را می‌دهد، به‌طوری که دو نقطهٔ به هم پیوسته هرگز رنگ یکسانی نداشته باشند. با پیوندهای کم، این کار آسان است. با پیوندهای زیاد، ناممکن می‌شود.

حالا گراف را تصادفی بسازید: n نقطه، که هر جفت از آن‌ها مستقلاً و با احتمالی کوچک به هم پیوند می‌خورند، به‌طوری که هر نقطه به‌طور میانگین d همسایه داشته باشد. با بزرگ‌تر شدن d، گراف تصادفی از حالت «تقریباً مطمئناً با q رنگ رنگ‌پذیر» به حالت «تقریباً مطمئناً نه» می‌رسد. این تغییر دقیقاً کجا رخ می‌دهد؟ این پرسش، برای هر تعداد ثابت رنگ q از سه به بالا، موضوع مقاله‌ای تازه از گایا کارنینی (Gaia Carenini)، در دانشگاه کمبریج (University of Cambridge)، است.

گذاری که شاید نوسان کند

در مقاله‌ای از سال 1999 که در فهرست منابع آمده است، آخلیوپتاس (Achlioptas) و فریدگوت (Friedgut) ثابت کردند که این گذار تیز است: برای هر اندازهٔ n، یک درجهٔ میانگین بحرانی d_q(n) وجود دارد، به‌طوری که اندکی پایین‌تر از آن، گراف تقریباً مطمئناً رنگ‌پذیر است و اندکی بالاتر از آن، تقریباً مطمئناً نه. پنجره‌ای که گذار در آن رخ می‌دهد تا هیچ کوچک می‌شود.

اما این یک روزنه باقی می‌گذاشت. هیچ چیز مانع نمی‌شد که خود مقدار بحرانی با بزرگ‌تر شدن گراف‌ها نوسان کند — برای گراف‌هایی با یک اندازه در جایی بنشیند، برای گراف‌های بزرگ‌تر اندکی جای دیگر، و هرگز تثبیت نشود. حدس همگرایی Achlioptas–Friedgut می‌گوید که چنین چیزی رخ نمی‌دهد: برای هر q، یک ثابت یکتای d_q وجود دارد که گراف‌های تصادفی پایین‌تر از آن رنگ‌پذیرند و بالاتر از آن نه.

آنچه فیزیک‌دانان پیش‌بینی کرده بودند

فیزیک آماری تصویری از آنچه رخ می‌دهد در دست داشت. با افزوده شدن پیوندها، رنگ‌آمیزی‌های معتبر در خوشه‌ها (clusters) گرد هم می‌آیند: رنگ‌آمیزی‌های درون یک خوشه به هم شبیه‌اند، در حالی که دو خوشه در نقطه‌های بسیاری با هم فرق دارند. سپس، در مرحله‌ای که چگالش (condensation) نامیده می‌شود، چند خوشهٔ بزرگ سهم چشمگیری از همهٔ رنگ‌آمیزی‌ها را در بر می‌گیرند — و تنها پس از آن است که مجموعهٔ رنگ‌آمیزی‌ها تهی می‌شود. این سازمان‌یابی توضیح می‌دهد که چرا استدلال‌های شمارشی در نزدیکی آستانه به دشواری می‌افتند.

برای تعداد زیاد رنگ‌ها، کارهای پیشین آستانه را در بازه‌ای باریک محصور کرده بودند: آستانه تقریباً میان 2q log q − log q − 2 log 2 و 2q log q − log q − 1 قرار دارد، یعنی شکافی به پهنای 2 log 2 − 1 با بزرگ شدن q. اما «باریک» به معنای «ثابت» نیست، و برای تعداد کم رنگ‌ها، مانند سه، این پرسش باز مانده بود.

مسئله‌ای دوقلو، که نخست به آن پرداخته شد

رنگ‌آمیزی دوقلویی دارد: صدق‌پذیری (satisfiability)، یعنی مسئلهٔ انتخاب مقدارهای درست یا نادرست برای متغیرها به‌طوری که فهرستی از قیدهای منطقی تصادفی همگی برقرار باشند. آنجا هم می‌دانستند که آستانه‌ای تیز وجود دارد، بی‌آنکه اثباتی در دست باشد که تثبیت می‌شود. در گزارشی از سال 2026 که در مقاله به آن ارجاع شده، کارنینی اثباتی را اعلام کرد که آستانه تثبیت می‌شود، برای هر طول قید از سه به بالا، با نشان دادن اینکه پنجرهٔ گذار بسیار باریک است. مقالهٔ تازه همان استدلال را برای رنگ‌آمیزی سازگار می‌کند.

جفت‌هایی که با هم منجمد شده‌اند

اثبات از راه زنجیره‌ای از کاهش‌ها پیش می‌رود. با افزودن یکی‌یکی پیوندهای تصادفی، فرض کنید H لحظه‌ای باشد که گراف دیگر رنگ‌پذیر نیست. اگر H از یک گراف تصادفی به گراف دیگر کم تغییر کند — در پنجره‌ای به اندازهٔ حدود n/(log n)² پیوند — آنگاه آستانه باید تثبیت شود. یک نابرابری کلاسیک این را به پرسشی دربارهٔ آخرین گراف رنگ‌پذیر تبدیل می‌کند: این گراف به‌طور میانگین چند پیوند تصادفی تازه را تاب می‌آورد؟

اینجا مفهوم کلیدی وارد می‌شود: جفت‌های منجمد (frozen pairs). دو نقطه یک جفت منجمد می‌سازند وقتی هر رنگ‌آمیزی معتبری به آن‌ها رنگ یکسانی بدهد. یک پیوند تازه دقیقاً وقتی کشنده است که چنین جفتی را به هم وصل کند. تک‌نقطه‌ها را نمی‌توان روی رنگ خاصی منجمد کرد، چون جابه‌جا کردن رنگ‌ها همیشه رنگ‌آمیزی معتبر دیگری به دست می‌دهد؛ آنچه اجباری می‌شود رابطه‌ای میان دو نقطه است. کارنینی دنبال می‌کند که این رده‌های منجمد با افزوده شدن پیوندها چگونه رشد می‌کنند، با حذف یک پیوند یا یک نقطهٔ کامل و نگاه به انتخاب‌هایی که دوباره پدیدار می‌شوند. برآوردها نشان می‌دهند که آخرین گراف رنگ‌پذیر نمی‌تواند مدت زیادی دوام بیاورد، و همین پنجره را آن‌قدر باریک می‌کند که حدس اثبات شود.

آنچه ناشناخته می‌ماند

قضیه می‌گوید که آستانهٔ d_q برای هر q ≥ 3 وجود دارد. نمی‌گوید کجاست: مقاله هیچ مقداری برای آن نمی‌دهد، حتی برای سه رنگ. این مقاله پیش‌انتشاری با یک نویسندهٔ تنهاست و هنوز داوری همتا نشده است. در پایان آن بیانیه‌ای کوتاه آمده است که هیچ‌یک از استدلال‌های ریاضی‌اش توسط یک مدل زبانی بزرگ تولید نشده است.