الأسلوب الاحتمالي

لنفترض أن لدينا رسمًا بيانيًا كاملاً على${\displaystyle n}$الرؤوس . نريد أن نوضح (لقيم صغيرة بما يكفي من${\displaystyle n}$) أنه من الممكن تلوين حواف الرسم البياني بلونين (مثلاً الأحمر والأزرق) بحيث لا يوجد رسم بياني فرعي كامل على${\displaystyle r}$الرؤوس أحادية اللون (كل حافة ملونة بنفس اللون).

للقيام بذلك، نقوم بتلوين الرسم البياني عشوائياً. لون كل حافة بشكل مستقل باحتمالية${\displaystyle 1/2}$كونها حمراء و${\displaystyle 1/2}$من اللون الأزرق. نحسب العدد المتوقع للرسوم البيانية الفرعية أحادية اللون على${\displaystyle r}$الرؤوس كما يلي:

لأي مجموعة${\displaystyle S_{r}}$ل${\displaystyle r}$حدد المتغير من رؤوس الرسم البياني الخاص بنا${\displaystyle X(S_{r})}$يكون${\displaystyle 1}$إذا كانت كل حافة بين${\displaystyle r}$الرؤوس لها نفس اللون، و${\displaystyle 0}$وإلا. لاحظ أن عدد الألوان الأحادية${\displaystyle r}$-الرسوم البيانية الفرعية هي مجموع${\displaystyle X(S_{r})}$على جميع المجموعات الفرعية الممكنة${\displaystyle S_{r}}$لكل مجموعة فردية${\displaystyle S_{r}^{i}}$، القيمة المتوقعة لـ${\displaystyle X(S_{r}^{i})}$هو ببساطة احتمال أن يكون كل${\displaystyle C(r,2)}$الحواف في${\displaystyle S_{r}^{i}}$لها نفس اللون:

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

(عامل${\displaystyle 2}$(يحدث ذلك لوجود لونين محتملين).

وينطبق هذا على أي من${\displaystyle C(n,r)}$المجموعات الفرعية المحتملة التي كان بإمكاننا اختيارها، أي${\displaystyle i}$يتراوح من${\displaystyle 1}$ل${\displaystyle C(n,r)}$إذن لدينا أن مجموع${\displaystyle E[X(S_{r}^{i})]}$إجمالي${\displaystyle S_{r}^{i}}$يكون

${\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

مجموع التوقعات هو توقع المجموع ( بغض النظر عما إذا كانت المتغيرات مستقلة أم لا)، لذا فإن توقع المجموع (العدد المتوقع لجميع الألوان الأحادية) هو${\displaystyle r}$-الرسوم البيانية الفرعية) هو

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

فكّر فيما سيحدث إذا كانت هذه القيمة أقل من${\displaystyle 1}$بما أن العدد المتوقع من الألوان الأحادية${\displaystyle r}$-الرسوم البيانية الفرعية أقل من${\displaystyle 1}$يوجد تلوين يحقق الشرط التالي: عدد الألوان الأحادية${\displaystyle r}$-الرسوم البيانية الفرعية أقل من${\displaystyle 1}$عدد الألوان الأحادية${\displaystyle r}$عدد الرسوم البيانية الفرعية في هذا التلوين العشوائي هو عدد صحيح غير سالب ، وبالتالي يجب أن يكون${\displaystyle 0}$(${\displaystyle 0}$هو العدد الصحيح الوحيد غير السالب الأقل من${\displaystyle 1}$ويترتب على ذلك أنه إذا

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

(وهو ما ينطبق، على سبيل المثال، على${\displaystyle n=5}$و${\displaystyle r=4}$يجب أن يكون هناك تلوين لا يحتوي على ألوان أحادية${\displaystyle r}$-الرسوم البيانية الفرعية. ^{[ أ ]}

بحسب تعريف عدد رامزي ، فإن هذا يعني أن${\displaystyle R(r,r)}$يجب أن يكون أكبر من${\displaystyle n}$. بخاصة،${\displaystyle R(r,r)}$يجب أن ينمو على الأقل بشكل أُسّي مع${\displaystyle r}$.

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

تناولت ورقة بحثية لإردوش عام 1959 (انظر المرجع المذكور أدناه) المشكلة التالية في نظرية الرسم البياني : بالنظر إلى الأعداد الصحيحة الموجبة g و k ، هل يوجد رسم بياني G يحتوي فقط على دورات طولها g على الأقل ، بحيث يكون العدد اللوني لـ G على الأقل k ؟

يمكن إثبات وجود مثل هذا الرسم البياني لأي قيمتين لـ g و k ، والبرهان بسيط نسبيًا. لنفترض أن n قيمة كبيرة جدًا، ولنعتبر رسمًا بيانيًا عشوائيًا G على n رأسًا، حيث يوجد كل ضلع في G باحتمالية p = n ^{1/ g −1} . سنبين أن G يحقق الخاصيتين التاليتين باحتمالية موجبة:

الخاصية 1. يحتوي G على n /2 دورة على الأكثر طولها أقل من g .

البرهان. ليكن X عدد الدورات التي يقل طولها عن g . عدد الدورات التي طولها i في الرسم البياني الكامل ذي n رأسًا هو

${\displaystyle {\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}}$

وكل منها موجود في G باحتمال p ⁱ . وبالتالي، وفقًا لمتباينة ماركوف، لدينا

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

وبالتالي، بالنسبة لقيم n الكبيرة بما فيه الكفاية ، فإن الخاصية 1 تتحقق باحتمالية تزيد عن 1/2 .

الخاصية 2. لا تحتوي G على مجموعة مستقلة من الحجم${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$.

البرهان. ليكن Y حجم أكبر مجموعة مستقلة في G. من الواضح أن لدينا

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

متى

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}$وبالتالي، بالنسبة لـ n كبير بما فيه الكفاية ، فإن الخاصية 2 تتحقق باحتمالية تزيد عن 1/2 .

بالنسبة لـ n كبير بما فيه الكفاية ، فإن احتمال أن يكون للرسم البياني من التوزيع كلا الخاصيتين يكون موجبًا، حيث لا يمكن أن تكون الأحداث الخاصة بهذه الخصائص منفصلة (إذا كانت كذلك، فإن احتمالاتها ستصل إلى أكثر من 1).

وهنا تكمن الحيلة: بما أن G تمتلك هاتين الخاصيتين، يمكننا إزالة ما لا يزيد عن n /2 رأسًا من G للحصول على رسم بياني جديد G′ على${\displaystyle n'\geq n/2}$الرؤوس التي تحتوي فقط على دورات بطول لا يقل عن g . يمكننا أن نرى أن هذا الرسم البياني الجديد لا يحتوي على مجموعة مستقلة بحجم${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$. لا يمكن تقسيم G′ إلا إلى k مجموعة مستقلة على الأقل، وبالتالي، فإن عدد الألوان الخاص بها هو k على الأقل .

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