حدّ على الشبكات، مُثبت الآن لكل حجم

خذ بضع نقاط وصِل بعض أزواجها بخطوط. يسمّي الرياضيون هذا مخطّطًا (graph): النقاط رؤوسه، والخطوط أضلاعه، والمسافة بين رأسين هي أقل عدد من الأضلاع يلزم للانتقال من أحدهما إلى الآخر. والآن أضِف قاعدتين. يجب أن تكون المسافة بين كل زوج من الرؤوس 2 على الأكثر: موصولين مباشرة، أو عبر جار مشترك. ولا يجوز أن يكون أي ضلع زائدًا: احذف أي ضلع واحد، فيصبح زوج ما على بُعد أكثر من خطوتين. يُسمّى مثل هذا المخطّط حرجًا من القطر 2 (diameter-2-critical). فكم ضلعًا يمكن أن يحوي؟

سقف مانتل، وتخمين أجرأ

في عام 1907، أثبت Mantel أن مخطّطًا من n رأسًا لا مثلث فيه — أي لا توجد فيه ثلاثة رؤوس موصول كلٌّ منها بالآخرَين — يحوي ⌊n²/4⌋ ضلعًا على الأكثر: مربّع n مقسومًا على أربعة، مقرّبًا نزولًا إلى عدد صحيح. ولا يبلغ هذا السقف سوى مخطّط واحد، هو المخطّط الثنائي التجزئة التام المتوازن: مجموعتان متساويتان في الحجم قدر الإمكان، كل رأس في إحداهما موصول بكل رأس في الأخرى، ولا ضلع داخل أي مجموعة.

كل مخطّط خالٍ من المثلثات لا يمكن أن يُضاف إليه ضلع واحد آخر من دون أن ينشأ مثلث، هو مخطّط حرج من القطر 2. والعكس لا يصحّ: فبعض المخطّطات الحرجة من القطر 2 تحوي مثلثات.

مخطّط حرج من القطر 2 فيه 7 رؤوس و9 أضلاع، ويحوي المثلث v1v3v5. حذف v1v3 يقضي على المسار الوحيد ذي الخطوتين بين v2 وv3؛ وحذف ضلع خارج المثلث يترك طرفيه بلا مسار ذي خطوتين. — الشكل 1، Das وFox (2026)، arXiv:2610.39032.

وكان التخمين أن المثلثات لا تجلب شيئًا: فالمخطّط الحرج من القطر 2 ذو n رأسًا يحوي مع ذلك ⌊n²/4⌋ ضلعًا على الأكثر، ويبقى المخطّط الثنائي التجزئة التام المتوازن الوحيد الذي يبلغه. وتأتي مبرهنة مانتل عندئذ حالةً خاصة. وبالنسبة إلى الرؤوس السبعة في الشكل، يبلغ السقف 12 ضلعًا.

برج من الاثنينات

وفقًا لـErdős، كما نقل Zoltán Füredi، تعود المسألة إلى أعمال Ore في ستينيات القرن العشرين. وصاغ Ján Plesník حدّ الأضلاع حدسيةً عام 1975؛ واقترحها Murty وSimon على نحو مستقل وأضافا أن المخطّط الثنائي التجزئة التام المتوازن هو الحالة القصوى الوحيدة، ومن هنا حدسية مورتي–سايمون. وفي سبعينيات القرن العشرين وثمانينياته، أخذت حدود على الصورة c·n² تنخفض تدريجيًا، وc يقترب أكثر فأكثر من 1/4.

وفي عام 1992، أثبت Füredi الحدسية لكل n كبير بما يكفي، باستخدام طرائق الانتظام (regularity methods)، وهي أدوات مشتقّة من تمهيدية الانتظام لـSzemerédi. وكان الثمن هو الحجم الابتدائي: إذ كان على n أن يكون على الأقل برجًا من الاثنينات ارتفاعه نحو 10¹⁴، أي 2 أُسّ 2 أُسّ 2…، تُحسب من الأعلى إلى الأسفل — كل 2 مرفوع إلى قوة كل ما فوقه — مع نحو 10¹⁴ اثنينًا مكدّسة. وما دون هذا الحجم، لم تُحسم سوى عائلات خاصة من المخطّطات.

أضلاع في مقابل أضلاع غائبة

البرهان الجديد، الذي قدّمه Sanjana Das وJacob Fox من قسم الرياضيات في جامعة ستانفورد، يصحّ لكل n ابتداءً من 3. وهو يستخدم مطابقة عظمى (maximal matching): مجموعة من الأضلاع لا يشترك اثنان منها في رأس، ولا يمكن أن يُضاف إليها أي ضلع آخر من دون أن يلتقي ضلعان منها. والمطابقة على n رأسًا تحوي ⌊n/2⌋ ضلعًا على الأكثر.

التمهيدية الأساسية: في مخطّط حرج من القطر 2، ولـأي مطابقة عظمى، فإن الأضلاع الواقعة خارج المطابقة لا تزيد أبدًا عددًا على اللاأضلاع، أي أزواج الرؤوس غير الموصولة. والباقي حساب. فضعف عدد الأضلاع لا يتجاوز عدد الأزواج مضافًا إليه حجم المطابقة. ومع 10 رؤوس: 45 زوجًا زائد 5 أضلاع مطابقة على الأكثر تعطي 50، ومن ثمّ 25 ضلعًا على الأكثر. ولكل n، يساوي هذا المجموع بالضبط ضعف سقف مانتل.

والتمهيدية نفسها محاسبة دقيقة. فاللاضلع يكون حرجًا إذا كان مسار وحيد ذو خطوتين يصل بين طرفيه، كما هي حال اللاأضلاع الاثني عشر كلها في الشكل 1. ويربط المؤلفان كل لاضلع حرج بالضلعين في مساره، ويقسمان الشبكة الناتجة إلى قطع متصلة. وتحوي القطعة على الأكثر ضلعًا واحدًا زيادةً على لاأضلاعها الحرجة، ويجب أن تُدفع كلفة كل قطعة فيها هذا الفائض بلاضلع غير حرج. وللعثور على هذه اللاأضلاع، يستخدم المؤلفان مخارج المبادلة (switch exits): خذ ضلعًا أو لاضلعًا حرجًا من القطعة، واستبدل بأحد طرفيه شريكَ ذلك الطرف في المطابقة. فيُطالَب بكل لاضلع غير حرج مرتين على الأكثر، وتقدّم كل قطعة ذات فائض مطالبتين على الأقل، فيكتمل الحساب.

من وجد ماذا

«هذا البرهان وجده في معظمه ذكاء اصطناعي، وتحديدًا GPT-5.6 Sol، في 11 أغسطس 2026»، يكتب المؤلفان في بيان قصير عن الذكاء الاصطناعي. فقد وجد النموذج برهانًا كاملًا لحدّ ⌊n²/4⌋، بسّطه المؤلفان. وبالنسبة إلى عدد زوجي من الرؤوس، أثبت أيضًا أن المخطّط الثنائي التجزئة التام المتوازن هو الحالة القصوى الوحيدة، معتمدًا على حقيقة أثبتها Sumner عن المخطّطات التي تكون فيها كل مطابقة عظمى تامّة (perfect)، أي تغطّي كل الرؤوس.

ومع عدد فردي من الرؤوس، لا تكون أي مطابقة تامّة، وفي كثير من المخطّطات تُغفل كل مطابقة عظمى رأسًا واحدًا بالضبط: فلم يكن ممكنًا تكييف حجّة النموذج. فوجد المؤلفان برهانًا مختلفًا لحالة التساوي، يصحّ لكل n، وكتبا البحث بنفسيهما؛ وأفضت مراجعة أخيرة عبر GPT-6 Astra إلى «بضعة تعديلات طفيفة». والبحث نسخة أولية لم تخضع بعد لتحكيم الأقران، ولا يذكر أي نسخة من الحجّة جرى التحقّق منها حاسوبيًا.

عودة إلى عام 1907

إذا بلغ مخطّطٌ السقف، فإن المتباينة الأساسية تصبح مساواة لـكل مطابقة عظمى. وباختيار المطابقات بذكاء، يُبيّن المؤلفان أن مثل هذا المخطّط إما نجمة — رأس واحد موصول بكل الرؤوس الأخرى، ولا شيء غير ذلك — وإما أنه لا يحوي أي لاضلع حرج على الإطلاق. وفي المخطّط الحرج من القطر 2، يقع كل ضلع من أضلاع المثلث على مسار حرج ما، لذا فإن غياب اللاأضلاع الحرجة يعني غياب المثلثات؛ والنجمة لا تحوي مثلثًا أيضًا. فالمخطّط الذي يبلغ السقف خالٍ إذن من المثلثات، والخطوة الأخيرة هي المبرهنة التي سعت الحدسية إلى تقويتها: نتيجة مانتل عام 1907، التي تترك المخطّط الثنائي التجزئة التام المتوازن وحيدًا عند السقف.