משפט תומאסן על מעגלים זרים

משפט תומאסן על מעגלים זרים הוא משפט בתורת הגרפים שאומר שבגרף מכוון שהדרגה היוצאת של כל קודקוד בו גדולה מספיק, יש מספר גדול כרצוננו של מעגלים זרים. המשפט הוכח בשנת 1983 על ידי קרסטן תומאסן. בשנת 1996 הוכיח נוגה אלון גרסה הדוקה יותר של המשפט.

ניסוח המשפט

הניסוח מדויק של המשפט הוא:

קיימת פונקציה $f:\mathbb {N} \to \mathbb {N}$ כך שעבור כל מספר טבעי $n$, בכל גרף מכוון $\Gamma$ שדרגת היציאה של כל קודקוד בו היא לפחות $f(n)$, קיימים לפחות $n$ מעגלים מכוונים ב-$\Gamma$, שקבוצות קודקודיהם זרות בזוגות.

גרסאות הדוקות יותר

הוכחתו של תומאסן מראה שאפשר לבחור את $f$ להיות

$$f(k)=(k+1)!$$

תוצאה זאת רחוקה מלהיות הדוקה. תומסון מראה כי לכל $f$ מתאימה מתקיים:

$$f(k)\geq 2k-1.$$

הוא גם משער שאפשר לבחור את $f$ להיות

$$f(k)=2k-1.$$

אלון התקרב להוכחת השערה זאת והוכיח שאפשר לבחור את $f$ להיות

$$f(k)=64k.$$

עבור ערכים קטנים של $k$ אפשר לקבל תוצאות טובות יותר. לדוגמה, ההוכחה של תומאסן מראה כי עבור $k=2$ אפשר לבחור את $f(k)$ להיות 3.

במילים אחרות:

עבור כל גרף מכוון $\Gamma$ כך שדרגת היציאה של כל קודקוד ב- $\Gamma$ היא לפחות $3$, קימים לפחות $2$ מעגלים מכוונים ב-$\Gamma$ הזרים בקודקודיהם.

שימושים

המשפט משמש בין היתר לפתרון בעיה על פירוק של גרף לתת-קבוצות. הבעיה עלתה בקבוצת הפייסבוק "חפירות על מתמטיקה" ונפתרה על ידי נוגה אלון. הבעיה מדברת על שיבוץ תלמידים לכיתות. לפי תנאי הבעיה נאמר לכל אחד מהתלמידים שהוא יכול לבחור $k$ חברים, ומובטח לו שלפחות אחד מהם יהיה איתו בכיתה. השאלה היא האם קבוצה של תלמידים יכולה לתאם את הבחירות שלהם כך שבהכרח ישובצו בכיתה אחת. קל להראות שאם $k<3$ אז התשובה היא כן. אלון הוכיח באמצעות משפט תומאסן (עבור $n=2$) שאם $k\geq 3$ אז התשובה היא לא.

ראו גם

• חידת הכתה המופרעת - חידה קשורה בפורטל מתמטיקה של הוויקיפדיה העברית.