قفزة صغيرة كبيرة جدًا إلى الأمام في نظرية المخططات

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

أنتجت أرقام رامزي نظامًا كاملاً يسمى نظرية رامزي ، والتي تبحث عن أنماط لا مفر منها في مجموعة كبيرة من الأنظمة.

على سبيل المثال ، لنفترض أنك تحاول نشر جميع الأعداد الصحيحة بين عدد من المجموعات ، وتريد تجنب وضع تسلسلات من أرقام متباعدة بشكل متساوٍ في أي من المجموعات. تُظهر نظرية رامزي أنك ستفشل (إلا إذا كان لديك عدد لا نهائي من الجرافات). يمكن تطبيق النظرية على أي شيء يمكنك الاعتماد عليه. قال بيني سوداكوف ، عالم رياضيات في المعهد الفدرالي السويسري للتكنولوجيا في زيورخ ، إن الدرس الأساسي لهذه الدراسة هو أنه "لا يمكنك إنشاء نظام فوضوي بالكامل".

يحدد رقم رامزي حجم المثال النموذجي الذي يجب أن يكون عليه قبل ظهور أنماط معينة حتمًا. ولكن على الرغم من مركزيتها ، لم يتمكن أحد من حساب رقم Ramsey للجميع باستثناء أبسط الحالات. أفضل ما تمكنوا من فعله هو إيجاد حدود (أو حدود) لما قد يكون عليه الأمر. حتى في ذلك الوقت ، كان الحد الأعلى الذي أنشأه إردوس وأحد المتعاونين منذ ما يقرب من قرن من الزمان بالكاد يتزحزح.

بعد ذلك ، في ندوات 15 مارس ، وفي ورقة نُشرت في وقت لاحق من ذلك المساء ، أعلن الباحثون أنهم قاموا بتحسين الحد الأعلى لرقم رامزي بمقدار أسي.

قال: "لقد كنت على الأرض" يوفال ويجديرسون، عالم رياضيات في جامعة تل أبيب ، عند سماعه بالنتيجة الجديدة. "كنت أرتعش حرفيًا لمدة نصف ساعة إلى ساعة."

خطوط الحزب

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

الرسم البياني الكامل معقد وبسيط - كل عقدة متصلة بكل عقدة أخرى. يصف رقم Ramsey عدد العقد التي يجب أن يحتويها الرسم البياني الكامل لإجبارها على الحصول على بنية معينة. لنفترض أن حواف الرسم البياني الكامل قد تم تعيينها بلون واحد من لونين: أحمر أو أزرق. ولنفترض أنك تحاول تلوين الحواف بطريقة تتجنب ربط مجموعة من العقد بحواف من نفس اللون. في عام 1930 ، أثبت فرانك رامزي أنه إذا كان الرسم البياني كبيرًا بدرجة كافية ، فسيصبح من المستحيل تجنب إنشاء ما يسميه علماء الرياضيات الزمرة أحادية اللون - مجموعة من العقد التي تكون حوافها المشتركة إما حمراء أو زرقاء بالكامل.

ما هو حجم الرسم البياني بالضبط قبل أن تضطر زمرة أحادية اللون للظهور؟ الجواب يعتمد على حجم الزمرة. أظهر رامزي أن هناك عددًا ، يسمى الآن رقم رامزي ، يمثل الحد الأدنى من عدد العقد التي يجب أن توجد بها زمرة أحادية اللون ذات حجم معين ، بغض النظر عن كيفية تلوين الحواف.

لكن من الصعب تحديد حجم رقم رامزي. في عام 1935 ، بعد خمس سنوات من إثبات رامزي لوجوده ، قدم إردوس وجورج سزكيريس حدًا أعلى جديدًا أكثر إحكامًا حول حجم رقم رمزي لمجموعة ذات حجم معين. ولكن منذ ذلك الحين ، بالكاد تمكن علماء الرياضيات من تحسين حسابات إردوس وسيكيرس.

للحصول على حدس أفضل لما يعنيه هذا ، ضع في اعتبارك مثالًا كلاسيكيًا ، حيث تمثل العقد الضيوف في حفلة. قم بتلوين الحافة بين أي ضيفين باللون الأحمر إذا التقيا من قبل ، والأزرق إذا لم يلتقيا. يمكنك اختيار أي حجم زمرة تريده - قم بدعوة عدد كافٍ من الأشخاص إلى الحفلة ، ولا يمكنك تجنب دعوة مجموعة من الأشخاص يعرفون بعضهم البعض (زمرة في معاني متعددة للكلمة) أو دعوة مجموعة من الأشخاص الذين لم يلتق قط من قبل.

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

تعد أرقام رمزي القليلة الأولى سهلة الحساب نسبيًا. لنفترض أنك تريد معرفة حجم أصغر رسم بياني يجب أن يحتوي حتمًا على زمرة بحجم اثنين ، أو R (2) لعلماء الرياضيات. نظرًا لأن الرسم البياني الكامل الذي يحتوي على عقدتين هو فقط عقدتان متصلتان بحافة ، ويجب أن تكون هذه الحافة إما حمراء أو زرقاء ، فإن R (2) هي 2. بشكل عام ، R (k) ، أو عدد Ramsey من k، هو الحد الأدنى لعدد العقد التي لا يمكن للرسم البياني أن يتجنب بعدها احتواء مجموعة من الحجم k.

ليس من الصعب إظهار أن رقم رامزي لمجموعة بحجم 3 ، أو R (3) ، هو 6 (انظر الرسم). ولكن لم يكن حتى عام 1955 تم تثبيت R (4) على 18. R (5) لا تزال غير معروفة - إنها 43 على الأقل وليس أكبر من 48. على الرغم من أن هذه الأرقام صغيرة ، إلا أن غربلة جميع الألوان الممكنة قد انتهت حول السؤال ، قال ديفيد كونلون من معهد كاليفورنيا للتكنولوجيا. ضع في اعتبارك عدد الألوان على الرسم البياني الكامل المكون من 43 عقدة. "لديك 903 حواف ؛ كل من هؤلاء يمكن تلوينه بطريقتين ". "لذا تحصل على 2⁹⁰³، وهو كبير بشكل فلكي ".

مع زيادة حجم الزمرة ، تصبح مهمة تحديد رقم رامزي أكثر صعوبة. قال إردوس ساخرًا إن الحرب الشاملة مع كائنات فضائية متطلبة رياضيًا ستكون أسهل من محاولة ذلك الرقم R (6)، والتي تقع في مكان ما بين 102 و 165. ينمو نطاق عدم اليقين بسرعة: وفقًا لـ التقديرات التي جمعتها ستانيسلاف رادزيسزوفسكي، R (10) يمكن أن تكون صغيرة مثل 798 وكبيرة مثل 23,556،10. لكن أهداف علماء الرياضيات تتجاوز بكثير رقم رامزي XNUMX. إنهم يريدون صيغة تعطي تقديرًا جيدًا لـ R (k) ، أو حتى - أو على وجه الخصوص - عندما k كبير للغاية.

قال ويغدرسون: "لا أعرف شخصًا في حالة اندماج لم يفكر في هذه المشكلة قليلاً على الأقل". "أعتقد أن هذه المشكلة خاصة حقًا."

النظام في المحكمة

كان فرانك رامزي شخصية انتقائية رائعة توفي عندما كان عمره 26 عامًا. قبل أسابيع قليلة من وفاته ، كان وقائع جمعية لندن الرياضية نشرت الورقة الذي قدم فيه أرقام رمزي. لم يكن هذا العمل يتعلق بالرسوم البيانية ، ولكن حول مشكلة في المنطق الرياضي. أثبت رامزي أن البيان الذي يلبي شروطًا معينة يجب أن يكون صحيحًا على الأقل لبعض الوقت. كان أحد هذه الشروط وجود "عالم" كبير من السيناريوهات لاختبار البيان فيه. وكخطوة انطلاق لهذه النتيجة ، أظهر رامزي أن رقم رامزي محدود.

بعد خمس سنوات ، أظهر Erdős و Szekeres أن عدد Ramsey من k أقل من 4^k. وبعد 12 عامًا ، أظهر إردوس أنها أكبر من حوالي $ latex sqrt {2} ^ k $. للقيام بذلك ، قام بحساب فرص احتواء الرسم البياني ذي الحواف الملونة بشكل عشوائي على زمرة أحادية اللون. أصبحت هذه التقنية "الاحتمالية" مؤثرة بشكل كبير في نظرية الرسم البياني. كما حاصرت R (k) بين هدفين يتزايدان أضعافًا مضاعفة: $ latex sqrt {2} ^ k $ و $ latex 4 ^ k $.

مع مرور العقود ، حاول العديد من علماء الرياضيات تضييق الفجوة بين القيم المحتملة لرقم رامزي. نجح البعض: في عام 1975 ، جويل سبنسر ضاعف الحد الأدنى. وسلسلة أوراق بقلم كونلون, أندرو توماسون و اشوين ساه دفعت إلى أسفل الحد الأعلى بمعامل يبلغ حوالي $ latex 4 ^ {log (k) ^ 2} $ بحلول عام 2020. ولكن بالمقارنة مع أحجام الحدود على رقم Ramsey ، كانت هذه التعديلات صغيرة. على النقيض من ذلك ، فإن أي تخفيض إلى 4 في صيغة Erdős و Szekeres R (k) <4^k سيكون تحسنًا هائلاً ، ينمو بسرعة مثل k يحصل على أكبر.

قال "يبدو أنه مجرد سؤال صغير لطيف" روب موريس، عالم رياضيات في IMPA ، المعهد البرازيلي للرياضيات البحتة والتطبيقية ، في ريو دي جانيرو ، الذي شارك في تأليف النتيجة الجديدة مع Campos و Griffiths و Sahasrabudhe. "إنه أمر خفي بعض الشيء لتقديره. لكن الناس يهتمون بذلك حقًا ". ربما هذا بخس. "لو أثبتوا ذلك في عام 1936 ، لكان الناس سيقولون ، حسنًا ، ما هي المشكلة الكبيرة؟" قالت بيلا بولوباس ، التي كانت مستشارة الدكتوراه لموريس وساهاسرابوده في جامعة ممفيس. "منذ ذلك الحين ، ثبت أنها مشكلة كبيرة جدًا ، لأنه على مر السنين ، تمت كتابة عدة آلاف من الأوراق البحثية حول أشكال مختلفة من مشكلة رامزي." مثل ليانا يبريميان، عالم رياضيات في جامعة إيموري ، قال ، "أرقام رمزي تخلق هذا الجسر بين التوافقيات والاحتمالات والهندسة."

نظرية اللعبة

 في أغسطس 2018 ، كان Sahasrabudhe زميلًا لما بعد الدكتوراه تحت إشراف Morris في IMPA. كان الاثنان يأملان في بدء مشروع جديد مع غريفيث ، الذي يُدرِّس في الجامعة البابوية الكاثوليكية المجاورة ، عندما ورقة من كونلون لفت انتباههم. حددت الورقة استراتيجية ممكنة للحصول على تحسين أسي على رقم رامزي. بدأ غريفيث وموريس وساهاسربوده باللعب بالفكرة.

يتذكر ساهسربوده "لقد كان الأمر مثيرًا حقًا في البداية". قال إن الأمر استغرق منهم حوالي شهر فقط لوضع مخطط لحججهم.

كانت خطتهم هي البناء على الأفكار المستخدمة في إثبات Erdős و Szekeres الأصلي بأن $ latex R (k) <4 ^ k $. لإثبات أن رقم Ramsey هو على الأكثر $ latex 4 ^ k $ ، تخيل أنك تلعب لعبة على رسم بياني كامل مع عقد $ latex 4 ^ k $. اللعبة لها لاعبان. أولاً ، يقوم خصمك بتلوين كل حافة إما باللون الأحمر أو الأزرق ، على أمل تلوين الحواف بطريقة تتجنب إنشاء زمرة أحادية اللون من k العقد.

بمجرد أن ينتهي خصمك من التلوين ، فإن مهمتك هي البحث عن زمرة أحادية اللون. إذا وجدت واحدة ، ستفوز.

للفوز بهذه اللعبة ، يمكنك اتباع استراتيجية بسيطة. من المفيد التفكير (مجازيًا) في فرز العقد في مجموعتين. ستشكل العقد الموجودة في أحد الدلاء زمرة زرقاء ، وستشكل العقد الموجودة في الدلو الآخر زمرة حمراء. سيتم حذف بعض العقد ، ولن يتم السماع عنها مرة أخرى. في البداية ، تكون كلتا المجموعتين فارغتين ، وكل عقدة مرشحة للدخول في أي منهما.

ابدأ بأي عقدة تلفت انتباهك. ثم انظر إلى الحواف المتصلة. إذا كان نصف الحواف أو أكثر باللون الأحمر ، فاحذف كل الحواف الزرقاء والعقد المتصلة بها. ثم ضع اختيارك الأصلي في الدلو "الأحمر". كل الحواف الحمراء لهذه العقدة لا تزال حية وبصحة جيدة ، وتتشبث ببقية الرسم البياني من داخل الجرافة. إذا كان أكثر من نصف الحواف باللون الأزرق ، فإنك تحذف بشكل متماثل الحواف والعقد الحمراء ، وتضعها في الدلو الأزرق.

كرر حتى لا يتبقى لديك عقد. (نظرًا لاكتمال الرسم البياني ، يتم توصيل كل عقدة متبقية في أي نقطة بكلتا المجموعتين حتى يتم وضعها في أحدهما.)

عندما تنتهي ، انظر داخل الدلاء. نظرًا لأن العقدة دخلت الدلو الأحمر فقط بعد القضاء على جيرانها الأزرقين ، فإن جميع العقد الموجودة في الدلو الأحمر متصلة بحواف حمراء - تشكل زمرة حمراء. وبالمثل ، فإن الدلو الأزرق يشكل زمرة زرقاء. إذا كان الرسم البياني الأصلي يحتوي على عقد $ latex 4 ^ k $ على الأقل ، فمن الممكن إثبات أن إحدى هذه المجموعات يجب أن تحتوي على الأقل k العقد ، مما يضمن زمرة أحادية اللون في الرسم البياني الأصلي.

هذه الحجة ذكية وأنيقة ، لكنها تجعلك تبني مجموعتين - واحدة زرقاء والأخرى حمراء - على الرغم من أنك تحتاج واحدة فقط حقًا. وأوضح كونلون أنه سيكون من الأفضل أن تتحول إلى اللون الأحمر دائمًا. بموجب هذه الإستراتيجية ، ستختار عقدة في كل خطوة ، وتمسح حوافها الزرقاء ، ثم ترميها في الدلو الأحمر. عندئذٍ تمتلئ الدلو الأحمر بسرعة ، وستجمع زمرة حمراء k العقد في نصف الوقت.

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

امتحان كتاب مفتوح

في تحديث طريقة لعبهم ، اتبع Griffiths و Morris و Sahasrabudhe مسارًا أكثر التفافًا قليلاً. بدلاً من بناء زمرة أحادية اللون مباشرة عن طريق رمي العقد في دلاءهم الحمراء والزرقاء ، ركزوا أولاً على بناء هيكل يسمى الكتاب الأحمر.

يتكون الكتاب ، في نظرية الرسم البياني ، من جزأين: هناك زمرة أحادية اللون ، تسمى "العمود الفقري" ، ومجموعة ثانية مميزة من العقد تسمى "الصفحات". في الكتاب الأحمر ، تكون جميع الحواف التي تربط العقد داخل العمود الفقري باللون الأحمر ، وكذلك الحواف التي تربط العمود الفقري بالصفحات. ومع ذلك ، يمكن أن تكون الحواف التي تربط العقد داخل الصفحات أي مجموعة من الألوان. لاحظ كونلون في مقالته لعام 2018 أنه إذا تمكنت من العثور على زمرة حمراء داخل صفحات الكتاب ، فيمكنك دمجها مع العمود الفقري للحصول على زمرة حمراء أكبر. يتيح لك هذا تفكيك البحث عن زمرة حمراء كبيرة إلى عمليتي بحث أسهل. أولاً ، ابحث عن كتاب أحمر. ثم ابحث عن زمرة في صفحات الكتاب.

أراد Griffiths و Morris و Sahasrabudhe تعديل الخوارزمية الفائزة باللعبة بحيث قامت ببناء كتاب أحمر بدلاً من زمرة حمراء. على الرغم من أنهم استقروا على هذه الخطة بعد أسابيع فقط من مشروعهم ، إلا أن الأمر سيستغرق سنوات حتى يعمل. ما زالوا بحاجة لدرء خطر فقدان كل حوافهم الحمراء.

قال كامبوس ، الذي انضم إلى المشروع في عام 2021: "لقد علقنا لفترة طويلة جدًا".

في كانون الثاني (يناير) الماضي ، وافق علماء الرياضيات الأربعة على التحول إلى نسخة أخرى من المشكلة. يبدو هذا الإصدار أكثر تعقيدًا ، لكن اتضح أنه أسهل.

طوال الوقت ، كان الفريق يركز على رقم رمزي R (k) ، المعروف أيضًا باسم رقم رمزي "القطري". رسم بياني بحجم R (k) يجب أن يحتوي على k العقد ، كلها متصلة بحواف من نفس اللون ، ولكن لا يهم إذا كان هذا اللون أحمر أو أزرق. من ناحية أخرى ، فإن رقم رامزي "خارج القطر" R (k, l) يقيس حجم الرسم البياني قبل أن يحتوي على زمرة حمراء بها k العقد ، أو زمرة زرقاء بها l العقد. بدلاً من الاستمرار في حل المشكلة القطرية ، قررت المجموعة تجربة الإصدار غير المائل. أثبت هذا الوحي.

قال غريفيث: "لوقت طويل ، شعرت أن كل باب تدفعه كان إما مغلقًا بمسامير ، أو على الأقل يصعب الوصول إليه". "وبعد هذا التغيير ، شعرت أن كل باب كان مفتوحًا. بطريقة ما ، بدا أن كل شيء يعمل ". في الإصدار غير القطري ، وجدوا طريقة لحذف مجموعة من الحواف الزرقاء في وقت واحد باتباع بروتوكول معين ، مما أدى إلى زيادة كثافة الحواف الحمراء ، وأدى إلى تحسين الحد على رقم رمزي خارج القطر. هذه الطريقة ، التي تسمى وسيطة "زيادة الكثافة" ، تم استخدامها سابقًا لحل المشكلة مشاكل أخرى مهمة في التوافقية، ولكن لم يتم استخدامه في مشكلة رقم رمزي.

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

إبسيلون ، إبسيلون

بعد المحادثات في 16 مارس ، بدأ الحضور في تأكيد الشائعات. تم تداول الصور من حديث سهاسربوده من خلال المكالمات الهاتفية والرسائل الخاصة - حتى في مشاركة غامضة ولكنها موحية على مدونة عالم الرياضيات جيل كالاي. ادعى كامبوس وجريفيثس وساهاسرابوده وموريس أنهم أظهروا أن $ latex R (k) <3.993 ^ k $. في تلك الليلة ، المؤلفون الأربعة نشروا ورقتهم على الإنترنت، مما يسمح لعلماء الرياضيات برؤية الدليل الجديد بأنفسهم.

"أعتقد أن الكثيرين منا لم يتوقعوا رؤية مثل هذا التحسن في حياتنا ، بشكل أساسي" ، قال ماتيجا بوسيتش، عالم رياضيات في جامعة برينستون ومعهد الدراسات المتقدمة. "أعتقد أنها نتيجة مذهلة للغاية."

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

"إنه دليل بارع تمامًا ، ورائع تمامًا ، واختراق حقيقي. لذا أتوقع الآن أن يتم فتح البوابات "، قال بولوباس. أنا مقتنع بأنه في غضون ثلاث سنوات ، سيكون النقاش حول التحسينات الممكنة. هل يمكننا تحسين 3.993 إلى 3.9؟ ربما إلى 3.4؟ وماذا عن 3؟ "

يأتي الدليل الجديد في 56 صفحة ، وسيستغرق الأمر أسابيع حتى يتم التحقق من كل التفاصيل بشكل كامل من قبل مجتمع التوليفات. لكن الزملاء متفائلون. "هذه المجموعة من المؤلفين ، هم أناس جادون للغاية. وقال ويغدرسون: "إنهم أناس بارعون حقًا في الأشياء التقنية للغاية".

يوافق غريفيث على ذلك عندما يتعلق الأمر بالمتعاونين معه. "إنه لشرف كبير أن أعمل مع أناس لامعين ، أليس كذلك؟ وأعتقد أن هذا هو ما أشعر بالامتنان الشديد له. "إذا تركوا الأمر لي ، فربما استغرقت خمس سنوات أخرى للحصول على التفاصيل بشكل صحيح."