عالم الرياضيات الروسي يدحض فرضية عمرها 53 عامًا حول تلوين الشبكات

كانت هناك حاجة لثلاث صفحات فقط لعالم الرياضيات الروسي لوصف طريقة لتلوين شبكات من نوع معين فاق توقعات الخبراء

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

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

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

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

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

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

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

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

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

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

Hangouts الملونة

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

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


اكتشف ياروسلاف شيتوف مثالًا مضادًا لفرضية هيدتنيمي البالغة من العمر 53 عامًا من نظرية الرسوم البيانية

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

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

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

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

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

ومع ذلك ، على مدار أكثر من 50 عامًا ، لم يتمكن علماء الرياضيات من العثور على منتج واحد للموتر ، للتلوين الذي يتطلب ألوانًا أقل من أي من الرسوم البيانية المكونة له. لقد تمكنوا من إثبات أن الفرضية صحيحة إذا لم تكن هناك حاجة إلى أكثر من أربعة ألوان لتلوين أحد الرسوم البيانية. وينطبق ذلك أيضًا على الحالة الأكثر عمومية للألوان "الكسرية" ، عندما يمكن تعيين كل قمة بمزيج من الألوان - على سبيل المثال ، الأصفر 2/3 والأخضر 1/3. (فيما يتعلق بتجمعات عطلة نهاية الأسبوع ، قد يتوافق هذا مع موقف يوجد فيه ثلاثة صحفيين في قائمة أصدقائك ، أحدهم يلعب التنس ، ودعيت اثنين منهم إلى عطلة نهاية الأسبوع "الصفراء" ، والثالثة إلى "الخضراء").

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

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

صفحات التلوين

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

يبدأ Shitov عمله من خلال مراقبة ما سيحدث إذا قمنا بدمج الرسم البياني G مع أحد الرسوم البيانية الأسية والحصول على منتج الموتر الخاص بهم. يحتوي الرسم البياني الأسي على عقدة واحدة لكل من الألوان الممكنة G مع عدد محدد من الألوان (جميع الألوان الممكنة مسموح بها ، وليس فقط تلك التي لها رؤوس مختلفة لها ألوان مختلفة). إذا كان الرسم البياني G ، على سبيل المثال ، يحتوي على 7 رؤوس ، وهناك 5 ألوان في لوحة الألوان لدينا ، فسيكون للرسم الأسي 5 ⁷ رؤوس - ولهذا السبب يطلق عليه الأسي.


ظلت فرضية ستيفن هيديتنيمي حول الحد الأدنى لعدد الألوان لتلوين منتج التينور من الرسوم غير مؤكدة منذ أكثر من 50 عامًا

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

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

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

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

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

الرسوم البيانية لشيتوف عملاقة: لم يحسب حجمها بالضبط ، لكن يقدر أن الرسم البياني G ربما يحتوي على حوالي ⁴¹⁰⁰ رأسًا ، وسوف تحتوي الرسوم البيانية الأسية على ⁴⁰⁰⁰ رأس على الأقل ، أي أكثر بكثير من العدد التقريبي للجزيئات الأولية في الكون يمكن ملاحظته [ حوالي 10 ⁸⁰ / تقريبا. العابرة. ].

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

وعلى الرغم من أنه من غير المحتمل أن تكون قادرًا على دعوة ^{4000 شخص} إلى منزلك الريفي ، فإن عمل Shitov لا يرفض وجود أمثلة مضادة بحجم أصغر كثيرًا. ولكن الآن ، بعد أن علم علماء الرياضيات أن فرضية Hedetniemi خاطئة ، فإن السؤال الطبيعي سيكون إلى أي مدى هو خاطئ تمامًا: كيف يمكن أن تكون هناك حاجة إلى عدد أقل من الألوان لتلوين منتج tensor مقارنة بالرسوم البيانية المكونة له ، وما هو الحد الأدنى لعدد العقد والحواف التي يمكن أن تتضمنها هذه الأمثلة المضادة؟

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