קבוצה בלתי תלויה (תורת הגרפים)

קבוצה בלתי תלויה היא קבוצה של נקודות (קודקודים) בגרף. נקודות בקבוצה כאלו לא מחוברות זו לזו. אם צובעים את הקודקודים כך ששכנים לא מקבלים את אותו צבע, כל צבע נותן קבוצה כזו. סימול נפוץ לגודל הגדול ביותר הוא α של הגרף. השאלה: האם יש קבוצה בלתי תלידה בגודל מסוים? זו שאלה קשה מאוד. ריצ'רד קארפ הראה שהי...