הלמה של שפרנר

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

הצגת הבעיה

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

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

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

הכללה

קיימת הכללה של הלמה למימד טבעי כלשהו עבור צביעה של קודקודי טריאנגולציה של סימפלקס ממדי. במקרה כזה, צביעת שפרנר (Sperner's Coloring) מוגדרת כצביעה של קודקודי טריאנגולציה מסוימת של הסימפלקס ה ממדי, כך ש

  1. נקודות השייכות לפאות החיצוניות של הסימפלקס צבועות בצבעים שונים. כלומר, אם הסימפלקס הוא קמור (convex hull) של הנקודות , ניתן לומר שהצבע של הוא
  2. נקודות השייכות לתת סימפלקס מממד , כלומר נקודות הנמצאות בתת-סימפלקס שהוא הקמור של חלק מן הנקודות , נאמר צבוע אך ורק על ידי הצבעים (זה האנלוג הרב ממדי לדרישה במימד 3 שכל נקודה הנמצאת באמצע צלע חיצונית צבועה בהתאם לאחד משני הקצוות).

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

הוכחה

נסמן ב את מספר המשולשים הקטנים הצבעוניים. נוכיח ש אי־זוגי ובפרט אינו 0. נסתכל על קבוצת המשולשים הקטנים הכולל גם את המשולש המשלים של המשולש הגדול כאשר פורסים אותו על ספירה וקדקודיו הם , נכנה שני משולשים מקבוצה זו "חברים" אם הם שכנים (כלומר עם צלע משותפת) וקודקודיהם המשותפים צבועים בשני הצבעים .

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

  1. למשולש המשלים יש מספר אי זוגי של "חברים" כי לאורך הצלע בין ל הצבע מתחלף מספר אי זוגי של פעמים וכל פעם כזו מוסיפה חבר.
  2. סכום מספר החברים של כל המשולשים הוא זוגי כי כל יחס "חברות" נספר פעמיים.

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

ראו גם

לקריאה נוספת

  • Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory, New York: Cambridge University Press, 2007. מסת"ב 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.
  • "הטכניון - מכון טכנולוגי לישראל המחלקה להוראת הטכנולוגיה והמדעים מתמטיקה צבעונית - הלמה של שפרנר פרופ' עמוס אלטשולר - משחק מתמטי".(הקישור אינו פעיל)

הערות שוליים

  1. ^ (Christos H. Papadimitriou, On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0