نظریه گراف افراطی
نظریه گراف افراطی میپرسد که یک گراف تا چه اندازه میتواند بزرگ یا متراکم باشد در حالی که از یک زیرساختار مشخص اجتناب کند، و پیکربندیهای افراطی را شناسایی میکند.
Definition
مطالعه حداکثر یا حداقل مقدار یک پارامتر گراف، مانند تعداد یالها، تحت یک محدودیت ساختاری مانند عدم وجود یک زیرگراف ثابت.
Scope
این موضوع بر مسائل نوع توران متمرکز است - حداکثر تعداد یالها در یک گراف بدون زیرگراف معین - که با قضایای مانتل و توران آغاز میشود و به قضیه اردوش-استون گسترش مییابد، که چگالی افراطی مجانبی را برای هر زیرگراف ممنوعه تعیین میکند. این موضوع به تعامل چگالی، ساختار و روش منظمسازی شمرودی میپردازد.
Core questions
- حداکثر تعداد یالها در یک گراف با n رأس که شامل هیچ نسخهای از یک زیرگراف معین نیست، چقدر است؟
- کدام گرافها به این حدود افراطی دست مییابند؟
- عدد رنگی یک زیرگراف ممنوعه چگونه پاسخ مجانبی را کنترل میکند؟
- روشهای منظمسازی چگونه گرافهای متراکم را به ساختار محدود کاهش میدهند؟
Key concepts
- زیرگرافهای ممنوعه
- گراف توران
- قضیه مانتل
- عدد افراطی (عدد توران)
- قضیه اردوش-استون
- لم منظمسازی شمرودی
Key theories
- قضیه توران
- در میان تمام گرافهای با n رأس که هیچ زیرگراف کامل با r+1 رأس ندارند، گراف کامل r-بخشی متوازن بیشترین یال را دارد، که حد بدون مثلث مانتل را تعمیم میدهد و نظریه گراف افراطی را پایهگذاری میکند.
- قضیه اردوش-استون
- برای هر زیرگراف ممنوعه ثابت H، حداکثر چگالی یال یک گراف بدون H به صورت مجانبی توسط عدد رنگی H تعیین میشود، که نتایج افراطی نوع توران را یکپارچه میکند.
Clinical relevance
نتایج چگالی افراطی، ساختار شبکههای بزرگ و سیستمهای محدودیت را محدود میکنند، و روش منظمسازی که در این زمینه توسعه یافته است، کاربردهایی در تست ویژگی، علوم کامپیوتر نظری و ترکیبیات جمعی دارد.
History
حد بدون مثلث مانتل در سال ۱۹۰۷ و تعمیم توران در سال ۱۹۴۱ این رشته را راهاندازی کردند؛ نظریه اردوش-استون-سیمونوویتس و لم منظمسازی شمرودی آن را به یک ستون مرکزی ترکیبیات مدرن تبدیل کردند.
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- مسئله نوع توران چیست؟
- این مسئله میپرسد که یک گراف میتواند حداکثر چند یال داشته باشد در حالی که از یک زیرگراف ثابت اجتناب کند؛ مثال کانونی آن حداکثر یالها در یک گراف بدون مثلث است.
- نظریه گراف افراطی چه ارتباطی با نظریه رمزی دارد؟
- هر دو به مطالعه ساختار اجتنابناپذیر میپردازند، اما نظریه افراطی یک زیرگراف ممنوعه را ثابت میکند و یالها را به حداکثر میرساند، در حالی که نظریه رمزی یک ساختار تکرنگ را زمانی که گراف به اندازه کافی بزرگ باشد، تضمین میکند.