الشبكات العشوائية تكفّ عن قابلية التلوين عند كثافة ثابتة
خذ مخططًا (graph) — نقاطًا تصل بينها روابط — وعلبة ألوان. إن التلوين السليم (proper colouring) بـq لونًا يعطي كل نقطة لونًا من بين q لونًا بحيث لا تشترك نقطتان مترابطتان في لون واحد أبدًا. ومع روابط قليلة، يكون ذلك سهلًا. ومع روابط كثيرة، يصبح مستحيلًا.
والآن ابنِ المخطط عشوائيًا: n نقطة، يُربط كل زوج منها، باستقلال عن غيره، باحتمال صغير، بحيث يكون للنقطة d من الجيران في المتوسط. ومع تزايد d، ينتقل المخطط العشوائي من «قابل للتلوين بـq لونًا على نحو شبه مؤكد» إلى «غير قابل لذلك على نحو شبه مؤكد». فأين يحدث التحوّل بالضبط؟ هذا السؤال، لأي عدد ثابت من الألوان q ابتداءً من ثلاثة، هو موضوع ورقة جديدة لـGaia Carenini، في جامعة كامبريدج.
تحوّل قد يتذبذب
في ورقة من عام 1999 مذكورة في قائمة المراجع، أثبت Achlioptas وFriedgut أن الانتقال حادّ (sharp): فلكل حجم n، توجد درجة متوسطة حرجة d_q(n) بحيث يكون المخطط، دونها بقليل، قابلًا للتلوين على نحو شبه مؤكد، وفوقها بقليل، غير قابل لذلك على نحو شبه مؤكد. والنافذة التي يحدث فيها التحوّل تنكمش حتى تتلاشى.
لكن ذلك ترك ثغرة. فلا شيء كان يمنع القيمة الحرجة نفسها من التذبذب مع تزايد حجم المخططات — فتقع في موضع ما لمخططات بحجم معيّن، وفي موضع مختلف قليلًا لمخططات أكبر، ولا تستقر أبدًا. وتنص حدسية Achlioptas–Friedgut للتقارب على أن ذلك لا يحدث: فلكل q، يوجد ثابت واحد d_q، تكون المخططات العشوائية دونه قابلة للتلوين وفوقه غير قابلة لذلك.
ما تنبّأ به الفيزيائيون
كان لدى الفيزياء الإحصائية تصوّر لما يجري. فمع إضافة الروابط، تتجمّع التلوينات الصالحة في عناقيد (clusters): فالتلوينات داخل العنقود الواحد يشبه بعضها بعضًا، في حين يختلف عنقودان على نقاط كثيرة. ثم، في مرحلة تُسمى التكاثف، تضمّ حفنة من العناقيد الكبيرة حصة معتبرة من كل التلوينات — ولا تصبح مجموعة التلوينات خالية إلا بعد ذلك. وهذا التنظيم يفسّر لماذا تتعثّر حجج العدّ قرب العتبة.
وبالنسبة إلى عدد كبير من الألوان، كانت أعمال سابقة قد حصرت العتبة في نطاق ضيق: فهي تقع بين نحو 2q log q − log q − 2 log 2 و2q log q − log q − 1، أي في فجوة عرضها 2 log 2 − 1 مع تزايد q. لكن «ضيق» لا يعني «ثابتًا»، وبالنسبة إلى أعداد صغيرة من الألوان كالثلاثة، ظلّ السؤال مفتوحًا.
مسألة توأم، عولجت أولًا
للتلوين توأم: قابلية الإرضاء (satisfiability)، أي مسألة اختيار قيم «صحيح» أو «خطأ» لمتغيرات بحيث تتحقق جميع القيود في قائمة من القيود المنطقية العشوائية. وهناك أيضًا، كان وجود عتبة حادة معروفًا من دون برهان على أنها تستقر. وفي تقرير من عام 2026 مذكور في الورقة، أُعلن عن برهان من Carenini على أنها تستقر فعلًا، لكل طول للقيود ابتداءً من ثلاثة، وذلك بإثبات أن نافذة الانتقال ضيقة جدًا. والورقة الجديدة تكيّف تلك الحجة مع التلوين.
أزواج متجمّدة معًا
يمضي البرهان عبر سلسلة من الاختزالات. فبإضافة روابط عشوائية واحدًا تلو الآخر، لتكن H اللحظة التي يكفّ فيها المخطط عن أن يكون قابلًا للتلوين. فإذا كانت H لا تتغير إلا قليلًا من مخطط عشوائي إلى آخر — ضمن نافذة من نحو n/(log n)² رابطًا — فلا بد أن تستقر العتبة. وتحوّل متباينة كلاسيكية ذلك إلى سؤال عن آخر مخطط قابل للتلوين: كم رابطًا عشوائيًا جديدًا يصمد أمامه في المتوسط؟
وهنا يأتي المفهوم المفتاحي: الأزواج المتجمّدة (frozen pairs). فتشكّل نقطتان زوجًا متجمّدًا حين يعطيهما كل تلوين صالح اللون نفسه. ويكون الرابط الجديد قاتلًا تحديدًا حين يصل بين زوج كهذا. ولا يمكن أن تتجمّد نقطة منفردة على لون بعينه، لأن تبديل الألوان فيما بينها يعطي دائمًا تلوينًا صالحًا آخر؛ فما يُفرض هو علاقة بين نقطتين. ويتتبّع برهان Carenini كيف تنمو هذه الفئات المتجمّدة مع إضافة الروابط، بحذف رابط أو نقطة بأكملها والنظر في الخيارات التي تعود إلى الظهور. وتُظهر التقديرات أن آخر مخطط قابل للتلوين لا يمكنه الصمود طويلًا، وهو ما يضيّق النافذة بما يكفي لإثبات الحدسية.
ما يبقى مجهولًا
تقول المبرهنة إن العتبة d_q موجودة لكل q ≥ 3. لكنها لا تقول أين تقع: فالورقة لا تعطي لها أي قيمة، حتى لثلاثة ألوان. والورقة نسخة أولية (preprint) فردية التأليف، ولم تخضع لتحكيم الأقران. وتنتهي بتصريح قصير بأن أيًّا من حججها الرياضية لم يُولَّد بواسطة نموذج لغوي كبير.
