הלמה של שפרנר

הלמה של שפרנר עוסקת בצביעות של משולשים והוכחה על ידי המתמטיקאי הגרמני עמנואל שפרנר ב-1928.

הצגת הבעיה

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

שימו לב כי בצלע החיצונית השמאלית הנקודות צבועות בהתאם לאחד הקצוות (אדום או ירוק), וכך גם בצלעות החיצוניות האחרות

באופן פורמלי, נסמן את קדקודי המשולש הגדול ב $V_{1},V_{2},V_{3}$ ונדרוש שהקודקוד $V_{i}$ צבוע בצבע $i\in \{1,2,3\}$. המשפט טוען שאם הקדקודים שעל צלע המשולש הגדול בין $V_{i}$ ל $V_{j}$ צבועים באחד משני הצבעים $i,j$, אז קיים משולש קטן "צבעוני" כלומר כל אחד מקודקודיו צבוע בצבע שונה.

הכללה

קיימת הכללה של הלמה למימד $d\in \mathbb {N}$ טבעי כלשהו עבור צביעה של קודקודי טריאנגולציה של סימפלקס $d$ ממדי. במקרה כזה, צביעת שפרנר (Sperner's Coloring) מוגדרת כצביעה של קודקודי טריאנגולציה מסוימת של הסימפלקס ה $d$ ממדי, כך ש

1. נקודות השייכות לפאות החיצוניות של הסימפלקס צבועות בצבעים שונים. כלומר, אם הסימפלקס הוא קמור (convex hull) של הנקודות $\left(P_{i}\right)_{i=0}^{d}\in \mathbb {R} ^{d}$, ניתן לומר שהצבע של $P_{i}$ הוא $i$
2. נקודות השייכות לתת סימפלקס מממד $k$, כלומר נקודות הנמצאות בתת-סימפלקס שהוא הקמור של חלק מן הנקודות $\left(P_{i}\right)_{i=0}^{d}\in \mathbb {R} ^{d}$, נאמר $P_{i_{1}},\dots P_{i_{k}}$ צבוע אך ורק על ידי הצבעים $i_{1},\dots i_{k}$ (זה האנלוג הרב ממדי לדרישה במימד 3 שכל נקודה הנמצאת באמצע צלע חיצונית צבועה בהתאם לאחד משני הקצוות).

במקרה כזה, קובעת למת שפרנר שמספר הסימפלקסים שצבועים בכל הצבעים (multicolored) הוא אי זוגי.

הוכחה

נסמן ב $K$ את מספר המשולשים הקטנים הצבעוניים. נוכיח ש $K$ אי־זוגי ובפרט אינו 0. נסתכל על קבוצת המשולשים הקטנים $T_{1},T_{2},...,T_{n}$ הכולל גם את המשולש המשלים של המשולש הגדול כאשר פורסים אותו על ספירה וקדקודיו הם $V_{1},V_{2},V_{3}$, נכנה שני משולשים מקבוצה זו "חברים" אם הם שכנים (כלומר עם צלע משותפת) וקודקודיהם המשותפים צבועים בשני הצבעים ${1,2}$.

לכל משולש "צבעוני" (מלבד המשולש המשלים) יש חבר אחד ויחיד, למשולשים שצבועים בצבעים ${1,2}$ יש שני חברים, ולכל השאר (מלבד אולי המשולש המשלים) – אין "חברים" כלל. בפרט מבין המשולשים הקטנים רק ל"צבעוניים" יש מספר אי זוגי של חברים. נשים לב ש:

1. למשולש המשלים יש מספר אי זוגי של "חברים" כי לאורך הצלע בין $V_{1}$ ל $V_{2}$ הצבע מתחלף $1\leftrightarrow 2$ מספר אי זוגי של פעמים וכל פעם כזו מוסיפה חבר.
2. סכום מספר החברים של כל המשולשים $T_{1},T_{2},...,T_{n}$ הוא זוגי כי כל יחס "חברות" נספר פעמיים.

נובע כי $K$ אי־זוגי כנדרש.

ראו גם

• משפט נקודת השבת של בראואר
• הלמה של קנסטר-קורטובסקי-מזורקביץ'
• מחלקת הסיבוכיות PPAD שמציאת המשולש הצבעוני היא בעיה שלמה עבורה.

לקריאה נוספת

• Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory, New York: Cambridge University Press, 2007. ISBN 978-0-521-87282-9
• K.T. Atanassov On Sperner's Lemma ,Stud. Sci. Math. Hungarica (volume=32, pages=71–74

קישורים חיצוניים

מדיה וקבצים בנושא הלמה של שפרנר בוויקישיתוף

• "הלמה של שפרנר-משחק מתמטי". אורכב מ-המקור ב-2004-09-28. נבדק ב-2010-01-09.
• "הטכניון - מכון טכנולוגי לישראל המחלקה להוראת הטכנולוגיה והמדעים מתמטיקה צבעונית - הלמה של שפרנר פרופ' עמוס אלטשולר - משחק מתמטי".(הקישור אינו פעיל)
• הלמה של שפרנר, באתר MathWorld (באנגלית)