الرقم اللوني للرسوم البيانية العشوائية الكثيفة جداً

تمت دراسة الرقم اللوني لرسم بياني عشوائي كثيف جداً G (n, p)، حيث p = 1 - n^-c لبعض الثوابت c > 0، أولاً من قبل سوريا ووارنكي، اللذان افترضا أن الانحراف النموذجي لـ (G (n, p) ) عن متوسطه هو من الرتبة ᵣ، حيث يتقلب بنحو (ᵣ)، حيث ᵣ هو عدد المجموعات المستقلة المتوقع بحجم r، و r هو الحد الأقصى بحيث ᵣ > 1، باستثناء عندما ᵣ = O (n). كما أثبتوا أيضاً افتراضهم في الحالة التي يكون فيها n^-2 1 - p = O (n^-1). في هذه الورقة، ندرس (G (n, p) ) في النطاق n^-1 n 1 - p n^-2/3، أي عندما يكون أكبر مجموعة مستقلة لـ G (n, p) عادة بحجم 3. نحن نثبت في هذه الحالة أن (G (n, p) ) مركزة على بعض الفترات ذات الطول O (₃)، حيث O (n^3/2 (1-p) ^3/2) = O (₃) مع احتمال مرتفع. علاوة على ذلك، لعائلة كبيرة من p (n)، هناك ولوظائف p = p (n) 'ناعمة' بما يكفي، هناك عدد لا نهائي من قيم n بحيث لا تكون (G (n, p) ) مركزة على أي فترة بحجم o (₃). كما نظهر أن (G (n, p) ) تلبي نظرية الحد المركزي في النطاق n^-1 n 1 - p n^-7/9.