لغز في المخططات من ستينيات القرن الماضي يُحسم أخيرًا

خذ بعض النقاط وصِل بعض أزواجها بخطوط: يسمّي الرياضيون ذلك مخططًا (غرافًا)، والنقاط رؤوسه والخطوط أضلاعه. والدورة حلقة مغلقة تمرّ برؤوس متمايزة وتعود إلى نقطة انطلاقها. والسؤال الطبيعي هو: هل يمكن تقسيم أضلاع المخطط — باستخدام كل ضلع مرة واحدة بالضبط — إلى دورات؟

الجواب معروف منذ زمن بعيد، كما تذكّر الورقة: يكون ذلك ممكنًا تمامًا حين يلامس كل رأس عددًا زوجيًا من الأضلاع. وتُسمّى هذه المخططات أويلرية. والسؤال التالي هو: كم دورة نحتاج؟ وبالنسبة إلى المخططات التي لا تكفي فيها الدورات وحدها، يُسمح أيضًا بالأضلاع المنفردة بوصفها قطعًا.

الحدسية

في ستينيات القرن الماضي، خمّن إردوش وغالاي أن أضلاع كل مخطط ذي n رأسًا يمكن تقسيمها إلى عدد من الدورات والأضلاع المنفردة لا يتجاوز ما يتناسب مع n — ويُكتب O(n). وقد أدرجها إردوش في عدة من مجموعاته للمسائل المفتوحة. وتطلب حدسية ذات صلة لهايوش ألا يتجاوز عدد الدورات (n − 1)/2 في كل مخطط أويلري.

والخطي هو أفضل ما يمكن أن نأمل فيه: فقد بيّن إردوش أن بعض المخططات تحتاج إلى نحو 1.5 n قطعة. وكان السؤال: هل يكفي دائمًا ثابتٌ ما مضروبًا في n؟

خمسون عامًا من حدود تزحف ببطء

لاحظ إردوش وغالاي بنفسيهما طريقة بسيطة: إزالة أطول دورة مرة بعد مرة. وهي تعطي نحو n log n قطعة — وبحسب الورقة، ظل ذلك أفضل حدّ عام طوال نحو خمسين عامًا. وفي الآونة الأخيرة، خفّضه كونلون وفوكس وسوداكوف إلى n log log n، ثم بوتسيتش ومونتغمري إلى n log* n، حيث تنمو log* n — أي عدد المرات التي يجب فيها أخذ اللوغاريتم للنزول دون الواحد — ببطء لا يكاد يُتخيّل. وكانت هذه المقاربات تعمل على جولات، وكانت كل جولة تكلّف نحو n دورة، فظل عدد الجولات يتسلل دائمًا إلى العدّ النهائي. كما كانت الحدسية قد بُرهنت لعائلات خاصة، مثل المخططات العشوائية.

أوزان تدفع ثمن الحلقات

يبرهن الآن جيهون كيم، من معهد KAIST في كوريا الجنوبية، الحدسية: يوجد ثابت C بحيث ينقسم كل مخطط ذي n رأسًا إلى ما لا يزيد على Cn من الدورات والأضلاع. ونتيجةً لذلك، تصح حدسية هايوش حتى عامل ثابت.

يتخلى البرهان عن الجولات. فإجراء واحد يزيل الدورات والأضلاع واحدة تلو الأخرى، ويُضبط المجموع بكميتين تبقى كل منهما دون ثابتٍ مضروبٍ في n.

• كمون قائم على الدرجات. يحصل كل رأس على وزن يتناقص مع عدد أضلاعه، يساوي تقريبًا 1 / (الدرجة × log² الدرجة). وتكون الدورة ثقيلة إذا بلغ مجموع أوزان رؤوسها 1 على الأقل. وإزالة دورة ثقيلة تُخفّض “كمونًا” إجماليًا بمقدار 1 على الأقل، ولا يتجاوز هذا الكمون في البداية ثابتًا مضروبًا في n. لذلك لا يمكن إزالة الدورات الثقيلة إلا O(n) مرة.
• عدد الرؤوس. حين لا تبقى أي دورة ثقيلة، يكون المخطط “خفيفًا” — وتبيّن المبرهنة الجديدة الرئيسية أن المخطط الخفيف ذا الدرجات الكبيرة لا بد أن يحتوي على منطقة كثيفة شبه مغلقة. وتُقسَّم هذه المنطقة إلى عدد من الدورات والأضلاع يتناسب مع حجمها، وبعد ذلك يبقى جزء من خمسين على الأقل من رؤوسها بضلعين على الأكثر، فتخرج نهائيًا. ولأن كل رأس لا يمكنه الخروج إلا مرة واحدة، فإن هذا الجزء يكلّف أيضًا O(n).

داخل الأجزاء الكثيفة من المخطط، تُغلق أجزاء المسارات في دورة واحدة بواسطة مسارات وصل تمر عبر “الموسِّعات”؛ ويُبقي تلوين عشوائي مسارات الوصل الخاصة بالدورة الواحدة منفصلة. — الشكل 3، Kim (2026)، arXiv:2610.07840.

ولتقسيم تلك المناطق الكثيفة، يوسّع البرهان عُدّة بوتسيتش ومونتغمري المبنية على “الموسِّعات” (expanders) المتينة — وهي مخططات يملك فيها كل مجموعة من الرؤوس جيرانًا كثيرين — ويلوّن الرؤوس عشوائيًا بحيث لا تتصادم أبدًا مسارات الوصل الخاصة بالدورة نفسها.

ما لا يزال مفتوحًا

الثابت C هائل، ولم يحاول المؤلف تحسينه. ولا يزال إيجاد أفضل ثابت — الذي لا يقل عن 1.5 — مسألة مفتوحة، شأنها شأن الصيغة الدقيقة لحدسية هايوش وحدسية ذات صلة لغالاي حول تقسيم المخططات إلى مسارات. ولا تتطلب حيلة الأوزان إلا أوزانًا يتقارب مجموعها، ويقترح المؤلف أنها قد تنفع في مسائل تفكيك أخرى.

هذه ورقة أولية لمؤلف واحد، لم يتحقق منها تحكيم الأقران بعد.

تضارب المصالح. يصرّح المؤلف بأنه استعان على نطاق واسع بـChatGPT (OpenAI) وClaude (Anthropic) في تطوير الحجج وإعداد النص والأشكال، وبأنه تحقق من جميع النتائج ويتحمل المسؤولية الكاملة عن الورقة. والنص الذي تقرؤه كتبه Claude أيضًا.