حدس اردوش–فابر–لوواس: تفاوت میان نسخه‌ها

[[پرونده:Erdős–Faber–Lovász conjecture.svg|بندانگشتی|240px|یک مثال از این حدس:یک گراف شامل ۴ دسته (گروه)که هر کدام دارای ۴ راس و هر ۲ دستهٔ متمایز دلخواه در یک راس مشترک باشند را می‌توان با ۴ رنگ، رنگ آمیزی کرد.]]

 

 

این نظریه بیان می‌کند که: اجتماع k کپی از k دسته که هر ۲ دستهٔ متمایز دلخواه حداکثر در یک راس اشتراک دارند دارای عدد رنگی k است.

فرض کنید در یک دانشکدهٔ دانشگاه k کمیته وجود دارد و هر کدام هم شامل k نفر از اعضای هیئت علمی هستند و قرار است که همهٔ کمیته‌ها در یک اتاق با هم جلسه داشته باشند که در اتاق k صندلی وجود دارد. همچنین فرض کنید که‌اشـتراک هر ۲ کمیتهٔ متمایز دلخواه شامل ۱ نفر می‌شود. آیا ممکن است که اعضای کمیته‌ها را به صندلی‌هایی نسبت دهیم به طوری که هـر عضو در همه کمیته‌هایی که عضو آنها است روی صندلی ثابتی بنشیند؟

 

بهترین نتیجهٔ یافته شده تا به امروز این است که عدد رنگی این مسئله حداکثر <math>k + o(k)</math> <ref>کان (۱۹۹۲).</ref> است.