حدس اردوش–فابر–لوواس: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
صفحهٔ جدید: [[Image:Erdős–Faber–Lovász conjecture.svg|thumb|240px|یک مثال از این حدس:یک گراف شامل 4 دسته (گروه)که هر کدام دارای 4 راس ... |
بدون خلاصۀ ویرایش |
||
خط ۴:
حداد و تاردیف در سال 2004 این نظریه را به بیان دیگری و با مطرح کردن یک مثال از کمیته های موجود در دانشگاه ارایه کردند :
فرض کنید در یک دانشکده ی دانشگاه k کمیـته وجود دارد و هر کـدام هم شامـل k نفر از اعضای هیئت علمی هستند و قرار است که همه ی کمیته ها در یک اتاق با هم جلسه داشته باشند که در اتــاق k صندلی وجود دارد. همچنین فرض کنید که اشــتراک هر 2 کمــیته ی متمایز دلخواه شامل 1 نفر می شود. آیا ممکن است که اعضای کمیته ها را به صندلی هایی نسبت دهیم به طوری که هـر عضو در همه کمیته هایی که عضو آنها است روی صندلی ثابتی بنشیند؟
پاول اردوس ابتداً مبلغ 50 دلار (دلار امریکا) برای اثبات این حدس به عنوان جایزه قرار داده بود ولی بعداً آنرا به مبلغ 500 دلار افزایش داد .<ref>چانگ و گراهام (1998).</ref>
بهترین نتیجه ی یافته شده تا به امروز ایناست که عدد رنگی این مسئله حداکثر <math>k + o(k)</math> <ref>کان (1992).</ref> است.
اگر مسئله را راحتتر و با شرایط کمتری در نظر بگیریم، بدین صورت که اجازه ئهیم دسته ها در هر چند راسی که می خواهند، اشتراک داشته باشند؛ آنگاه
==See also==
* [[Erdős conjecture]]
|