كتب المقاس وتلوين الرسم البياني
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
المقاس وتلوين الرسم البياني (معلومة)
لأي أعداد صحيحة موجبة g و χ ، يوجد رسم بياني ذو مقاس g على الأقل ورقم لوني على الأقل χ ؛ على سبيل المثال، في الرسم البياني Grötzsch بدون مثلث ووالذي به العدد اللوني 4 وبتكرار شكل Mycielskian المستخدم فيه، ينتج عنه رسومات بدون لمثلث لها عدد لوني كبير . كان بول إيردوس أول من أثبت هذه النتيجة العامة، باستخدام الطريقة الاحتمالية . بتعبير أدق، أوضح أن رسمًا عشوائيًا على رؤوس n ، يتشكل باختيار مستقل للأضلاع بحيث كل ضلع يظهر بهذا الرسم باحتمال قدره n(1 − g)/g . بالتالي فإن هذا الرسم يحتوي على الأكثر n/2 من الدورات بطول g عالأكثر باحتمال يقترب من 1 عندما n تقترب إلى ما لا نهاية . لكن في هذه الحالة فإن هذا الرسم ليس لديه مجموعة مستقلة بحجم n/2k . فبالتالي فإن حذف رأس واحد من كل دورة قصيرة قد يؤدي إلى تناقض لكون أقصردوره به المعرف بالمقاس يكون أكبر من g . في حين مطلوب أن تكون كل فئة من ألوان التلوين صغيرة وتتطلب بالتالي ألوان k على الأقل في أي تلوين.
يمكن إنشاء رسومات بيانية صريحة، رغم أنها كبيرة الحجم وذات مقاس كبير وأرقام لونية، كرسومات توضيحية معينة من Cayley للمجموعات الخطية على الحقول المحدودة . تحتوي هذه الرسوم البيانية المميزة لـ Ramanujan أيضًا على معامل توسع كبير.
