معرفی کتاب
کتاب «منطق شگفتانگیز گرافهای تصادفی» نوشته جوئل اسپنسر، به بررسی قوانین صفر-یک در گرافهای تصادفی میپردازد. این کتاب در سال ۲۰۰۱ توسط انتشارات اسپرینگر در مجموعه الگوریتمها و ترکیبات منتشر شد.
مدل اردوش-رنی-گیلبرت
گرافهای تصادفی در این کتاب بر اساس مدل اردوش-رنی-گیلبرت تولید میشوند. در این مدل، رأسها از پیش مشخص هستند و برای هر جفت رأس، به صورت مستقل و با احتمالی مشخص، تصمیم گرفته میشود که آیا با یک یال به هم متصل شوند یا خیر.
- قوانین صفر-یک بیان میکنند که برای برخی ویژگیهای گراف، احتمال بروز آنها با افزایش اندازه گراف به صفر یا یک میل میکند.
- به عنوان مثال، احتمال وجود مثلث در گراف با افزایش اندازه آن به یک میل میکند، در حالی که احتمال وجود رأس جهانی به صفر میل میکند.
نتیجه اصلی کتاب
نتیجه کلیدی کتاب که توسط اسپنسر و ساهارون شلاه اثبات شده، این است که توانهای گویای عدد ۲ هرگز تابع آستانه نیستند. در این اثبات از بازی ارنفوخ-فرایسه به عنوان ابزار اصلی استفاده شده است.
«این کتاب خودکفا، خواندنی و با نگارش ظریف، برای نظریهپردازان احتمال و منطقدانان توصیه میشود.» — والنتین کولچین