تخمين هيديتنييمي

في نظرية المخططات ، تتعلق فرضية هيديتنييمي ، التي صاغها ستيفن تي. هيديتنييمي عام 1966، بالعلاقة بين تلوين المخططات والضرب الموتري للمخططات . وتنص هذه الفرضية على أن

${\displaystyle \chi (G\times H)=\min\{\chi (G),\chi (H)\}.}$

هنا${\displaystyle \chi (G)}$يشير إلى العدد اللوني للرسم البياني المحدود غير الموجه${\displaystyle G}$.

المتباينة χ( G × H ) ≤ min {χ( G ), χ( H )} بسيطة: إذا كانت G ملونة بـ k لونًا، فيمكن تلوين G × H بـ k لونًا باستخدام نفس التلوين لكل نسخة من G في حاصل الضرب؛ وبالمثل إذا كانت H ملونة بـ k لونًا. وبالتالي، فإن تخمين هيديتنييمي يُختزل إلى التأكيد على أنه لا يمكن تلوين حاصل الضرب الموتري بعدد قليل من الألوان بشكل غير متوقع.

تم اكتشاف مثال مضاد للتخمين بواسطة ياروسلاف شيتوف ( 2019 ) (انظر كالاي 2019 )، وبالتالي دحض التخمين بشكل عام. 

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

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

أُثبتت الحالة التالية بعد فترة طويلة من صياغة الفرضية، على يد الزهار وساور (1985) : إذا كان حاصل ضرب G × H قابلاً للتلوين بثلاثة ألوان، فلا بد أن يكون أحد G أو H قابلاً للتلوين بثلاثة ألوان أيضًا. وبالتحديد، تكون الفرضية صحيحة عندما يكون G أو H قابلاً للتلوين بأربعة ألوان (لأن المتباينة χ( G × H ) ≤ min{χ( G ), χ( H )} لا تكون دقيقة إلا عندما يكون G × H قابلاً للتلوين بثلاثة ألوان). في الحالات المتبقية، يكون كلا الرسمين البيانيين في حاصل الضرب الموتري قابلاً للتلوين بخمسة ألوان على الأقل، ولم يُحرز تقدم إلا في حالات محدودة للغاية.

الدالة التالية (المعروفة باسم دالة Poljak-Rödl ) تقيس مدى انخفاض العدد اللوني لمنتجات الرسوم البيانية ذات اللون n .

${\displaystyle f(n)=\min\{\chi (G\times H)\colon \chi (G)=\chi (H)=n\}}$

تُعادل تخمينات هيدتنييمي القول بأن f ( n ) = n . أما تخمينات هيدتنييمي الضعيفة فتنص ببساطة على أن الدالة f ( n ) غير محدودة. بعبارة أخرى، إذا أمكن تلوين حاصل الضرب الموتري لرسمين بيانيين بعدد قليل من الألوان، فإن هذا يستلزم وجود حدٍّ ما للعدد اللوني لأحد العوامل.

تنص النتيجة الرئيسية لـ ( Poljak & Rödl 1981 ) ، والتي تم تحسينها بشكل مستقل من قبل Poljak و James H. Schmerl و Zhu، على أنه إذا كانت الدالة f ( n ) محدودة، فإنها محدودة على الأكثر بـ 9. وبالتالي فإن إثبات حدسية هيديتنييمي للرسوم البيانية ذات 10 ألوان سيؤدي بالفعل إلى حدسية هيديتنييمي الضعيفة لجميع الرسوم البيانية.

تُدرس هذه الفرضية في سياق أوسع، وهو تماثلات الرسوم البيانية ، لا سيما بسبب علاقاتها المهمة بفئة الرسوم البيانية (حيث تُمثل الرسوم البيانية الكائنات، والتماثلات الأسهم). لأي رسم بياني ثابت K ، تُدرس الرسوم البيانية G التي تقبل تماثلاً مع K ، ويُكتب G → K. تُسمى هذه الرسوم أيضًا بالرسوم البيانية القابلة للتلوين بـ K لونًا. يُعمم هذا المفهوم المعتاد لتلوين الرسوم البيانية، إذ يتبين من التعريفات أن التلوين بـ k لونًا هو نفسه التلوين بـ K _k لونًا (أي تماثل في الرسم البياني الكامل ذي k رأسًا).

يُطلق على الرسم البياني K اسم الرسم البياني الضربي إذا كان لأي رسمين بيانيين G و H ، فإن حقيقة أن G × H → K تستلزم أن G → K أو H → K صحيحة. وكما هو الحال مع التلوين الكلاسيكي، فإن الاستلزام العكسي صحيح دائمًا: إذا كان G (أو H ، بشكل متناظر) قابلاً للتلوين بـ K لونًا، فإنه يمكن تلوين G × H بسهولة بـ K لونًا باستخدام القيم نفسها بغض النظر عن H. وبالتالي، فإن حدسية هيديتنييمي تُكافئ القول بأن كل رسم بياني كامل هو رسم بياني ضربي.

الحالات المعروفة المذكورة أعلاه تُكافئ القول بأن K1 وK2 وK3 هي رسوم بيانية ضربية. أما حالة K4 _فهي مفتوحة على _نطاق واسع . _{من جهة} أخرى ، عمّم هاغكفيست وآخرون (1988 ) برهان إل-زهار وساور ( 1985) لإثبات أن جميع الرسوم البيانية الدورية ضربية. لاحقًا، أثبت تارديف (2005) بشكل أعم أن جميع الزمر الدائرية Kn _/k حيث n/k < 4 هي ضربية. من حيث العدد اللوني الدائري χc ، يعني هذا أنه إذا كان _{χc (} G × H ) < 4 ، فإن χc ( G × H ) = min{ _{χc (} G ), χc ₍ G ) } . وقد أظهر وروشنا (2017) أن الرسوم البيانية الخالية من المربعات ضربية.

يمكن إنشاء أمثلة على الرسوم البيانية غير الضربية من رسمين بيانيين G و H غير قابلين للمقارنة من حيث ترتيب التشاكل (أي لا يتحقق أي من G → H أو H → G ). في هذه الحالة، إذا وضعنا K = G × H ، فمن البديهي أن G × H → K ، ولكن لا يمكن لأي من G أو H أن يقبل تشاكلاً في K ، لأنه عند دمجه مع الإسقاط K → H أو K → G ، سينتج تناقض.

بما أن حاصل الضرب الموتري للرسوم البيانية هو حاصل الضرب في نظرية الفئات ضمن فئة الرسوم البيانية (حيث تمثل الرسوم البيانية الكائنات والتشاكلات الأسهم)، يمكن إعادة صياغة التخمين بدلالة البناء التالي على الرسمين البيانيين K و G. الرسم البياني الأسي K ⊆ ^G هو الرسم البياني الذي تكون فيه جميع الدوال V(G) → V(K) رؤوسًا (وليس التشاكلات فقط)، وتكون فيه الدالتان f و g متجاورتين عندما

f (v) مجاور لـ g(v') في K ، لجميع الرؤوس المتجاورة v و v' من G.

على وجه الخصوص، توجد حلقة عند الدالة f (أي أنها مجاورة لنفسها) إذا وفقط إذا كانت الدالة تُعطي تشاكلاً من G إلى K. وبعبارة أخرى ، توجد حافة بين f و g كلما عرفت الدالتان تشاكلاً من G × K² ( الغطاء الثنائي المزدوج _لـ G ) إلى K.

الرسم البياني الأسي هو ^الكائن الأسي في فئة الرسوم البيانية. وهذا يعني أن التشاكلات من G × H إلى الرسم البياني K تُقابل التشاكلات من H إلى KG . علاوة على ذلك، يوجد تشاكل eval  : G × KG → K يُعطى بالعلاقة eval( v , f ⁾ = f ( v ) . تسمح هذه الخصائص بالاستنتاج بأن خاصية الضرب في K تُكافئ ( El-Zahar & Sauer 1985 ) العبارة التالية:

إما G أو K ^G قابلة للتلوين بـ K لون، لكل رسم بياني G.

بمعنى آخر، يمكن اعتبار حدسية هيديتنييمي بمثابة بيان حول الرسوم البيانية الأسية: لكل عدد صحيح k ، يكون الرسم البياني K = ^kG _إما قابلاً للتلوين بـ k لونًا، أو يحتوي على حلقة (أي أن G قابل للتلوين بـ k لونًا). ويمكن أيضًا اعتبار التشاكلات eval  : G × K _{= kG} → ^K = _k أصعب حالات حدسية هيديتنييمي: إذا كان حاصل ضرب G × H مثالًا مضادًا، فإن G × K ^{= kG} _سيكون أيضًا مثالًا مضادًا.

عند تعميم هذه الفرضية على الرسوم البيانية الموجهة، نجد أمثلة مضادة بسيطة، كما لاحظ بولياك ورودل (1981) . في هذه الحالة، يكون العدد اللوني للرسم البياني الموجه هو نفسه العدد اللوني للرسم البياني الأساسي، ولكن حاصل الضرب الموتري له نصف عدد الحواف بالضبط (بالنسبة للحواف الموجهة g→g' في G و h→h' في H ، فإن حاصل الضرب الموتري G × H له حافة واحدة فقط، من (g,h) إلى (g',h') ، بينما سيكون لحاصل ضرب الرسوم البيانية غير الموجهة الأساسية حافة بين (g,h') و (g',h) أيضًا). مع ذلك، تبين أن فرضية هيديتنييمي الضعيفة متكافئة في كل من الرسوم البيانية الموجهة وغير الموجهة ( تارديف وويلاو 2006 ) .

لا يمكن تعميم هذه المشكلة على الرسوم البيانية اللانهائية: فقد قدم هاينال (1985) مثالاً على رسمين بيانيين لانهائيين، يتطلب كل منهما عددًا غير قابل للعد من الألوان، بحيث يمكن تلوين حاصل ضربهما بعدد قابل للعد فقط من الألوان. وأثبت رينو (2013) أنه في الكون القابل للإنشاء ، لكل عدد أصلي لانهائي${\displaystyle \kappa }$يوجد زوج من الرسوم البيانية ذات عدد لوني أكبر من${\displaystyle \kappa }$بحيث يمكن تلوين منتجهم بعدد محدود من الألوان.

أثبت سابيدوسي (1957) مساواة مماثلة للجداء الديكارتي للرسوم البيانية، وأُعيد اكتشافها عدة مرات لاحقًا. كما تُعرف صيغة دقيقة للجداء المعجمي للرسوم البيانية . وقدّم دوفوس وساندز وودرو (1985) تخمينين أقوى يتعلقان بإمكانية التلوين الفريدة.

المصادر الأولية

• دوفوس، د .؛ ساندز، ب.؛ وودرو، ر. إي. (1985)، "حول العدد اللوني لحاصل ضرب الرسوم البيانية"، مجلة نظرية الرسوم البيانية ، 9 (4): 487-495 ، doi : 10.1002/jgt.3190090409 ، MR 0890239 .
• الزهار، م.؛ ساور، ن. (1985)، "العدد اللوني لحاصل ضرب رسمين بيانيين رباعيي اللون هو 4"، كومبيناتوريكا ، 5 (2): 121-126 ، doi : 10.1007/BF02579374 ، MR 0815577 ، S2CID 7659747  .
• هاغكفيست، ر.؛ هيل، ب .؛ ميلر، د. ج.؛ نيومان لارا، ف. (1988)، "حول الرسوم البيانية الضربية وتخمين الضرب"، كومبيناتوريكا ، 8 (1): 63-74 ، doi : 10.1007/BF02122553 ، hdl : 1828/1589 ، MR 0951994 ، S2CID 39731578  .
• هاجنال، أ. (1985)، " يمكن عدّ العدد اللوني لحاصل ضرب رسمين لونيين من النوع ℵ _{1 "،} كومبيناتوريكا ، 5 (2): 137-140 ، doi : 10.1007/BF02579376 ، MR 0815579 ، S2CID 27087122  .
• هيديتنييمي، س. (1966)، تماثلات الرسوم البيانية والآلات ، تقرير فني 03105-44-T، جامعة ميشيغان.
• بولجاك، س .؛ رودل، ف. (1981)، "حول العدد اللوني القوسي للرسم البياني الموجه"، مجلة نظرية التوافيق، السلسلة ب ، 31 (2): 190-198 ، doi : 10.1016/S0095-8956(81)80024-X.
• رينو، أ. (2013)، حدسية هيديتنييمي للرسوم البيانية غير القابلة للعد ، arXiv : 1307.6841 ، Bibcode : 2013arXiv1307.6841R.
• سابيدوسي، ج. (1957)، "الرسوم البيانية ذات المجموعة المعطاة والخصائص النظرية للرسوم البيانية المعطاة"، المجلة الكندية للرياضيات ، 9 : 515-525 ، doi : 10.4153/CJM-1957-060-7 ، MR 0094810 ، S2CID 124514137  .
• شيتوف، ياروسلاف (مايو 2019)، أمثلة مضادة لتخمين هيديتنييمي ، arXiv : 1905.02167.
• تارديف، سي. (2005)، "الرسوم البيانية المضاعفة والتشاكلات الداخلية شبه الشبكية في فئة الرسوم البيانية"، مجلة نظرية التوافيق، السلسلة ب ، 95 (2): 338-345 ، doi : 10.1016/j.jctb.2005.06.002.
• تارديف، سي.؛ ويلو، د. (2006)، "الأعداد اللونية لحاصل ضرب الرسوم البيانية: النسخ الموجهة وغير الموجهة لدالة بولياك-رودل"، مجلة نظرية الرسوم البيانية ، 51 (1): 33-36 ، doi : 10.1002/jgt.20117 ، S2CID 17489968 .
• وروشنا، م. (2017)، "الرسوم البيانية الخالية من المربعات هي ضربية"، مجلة نظرية التوافيق، السلسلة ب ، 122 : 479-507 ، arXiv : 1601.04551 ، doi : 10.1016/j.jctb.2016.07.007 ، S2CID 205930734 .

الدراسات الاستقصائية والمصادر الثانوية

• إمريش، ويلفريد؛ كلافزار، ساندي (2000)، رسوم بيانية للمنتجات: البنية والتعرف ، وايلي، ISBN 0-471-37039-8.
• كالاي، جيل (10 مايو 2019)، "ضجة في أخبار الصباح - ياروسلاف شيتوف: أمثلة مضادة لتخمين هيديتنييمي" ، التوافقية والمزيد.
• كلافزار، ساندي (1996)، "تلوين نواتج الرسوم البيانية: دراسة استقصائية"، الرياضيات المتقطعة ، 155 ( 1-3 ): 135-145 ، doi : 10.1016/0012-365X(94)00377-U ، MR 1401366 .
• ساور، ن. (2001)، "تخمين هيديتنييمي: دراسة استقصائية"، الرياضيات المتقطعة ، 229 ( 1-3 ): 261-292 ، doi : 10.1016/S0012-365X(00)00213-2 ، MR 1815610 .
• تارديف، كلود (2008)، "تخمين هيديتنييمي، بعد 40 عامًا" (ملف PDF) ، ملاحظات نظرية الرسم البياني في نيويورك ، 54 : 46-57 ، MR 2445666 ، مؤرشف من الأصل (ملف PDF) بتاريخ 12 يوليو 2021 ، تم استرجاعه بتاريخ 23 فبراير 2017 .
• تشو، شودينغ (1998)، "دراسة استقصائية حول حدسية هيديتنييمي"، المجلة التايوانية للرياضيات ، 2 (1): 1-24 ، doi : 10.11650/twjm/1500406890 ، MR 1609464 .

• إنجازٌ رائد في نظرية الرسوم البيانية ، نمبرفايل