למת הרגולריות של סמרדי

למת הרגולריות של סמרדי או בקיצור למת הרגולריות, היא משפט שימושי בקומבינטוריקה קיצונית שהתגלה על ידי המתמטיקאי ההונגרי אנדריי סמרדי (Endre Szemerédi). הלמה מאפשרת, בהינתן כל גרף (לא משנה כמה גדול הוא), לקרב אותו על ידי גרף בגודל קבוע, כשגודלו של הגרף המקרב נקבע רק על פי איכות הקירוב.

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

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

הגדרות

בהינתן גרף G, ושתי קבוצות קודקודים U,V, נגדיר את הצפיפות ביניהן על ידי $d(U,V)={\frac {e(U,V)}{|U||V|}}$ כאשר (e(U,V זה מספר הקשתות בין הקבוצות.

נאמר שהקבוצות ε-רגולריות אם לכל שתי תתי קבוצות $U'\subset U,V'\subset V$ המקיימות $|U'|>\epsilon |U|,|V'|>\epsilon |V|$ מתקיים d(U,V)-d(U',V')|<ε|. כלומר, הצפיפות של כל שתי תתי קבוצות גדולות מספיק דומה לצפיפות של הקבוצות הגדולות. המשמעות האינטואיטיבית של זה היא שהקשתות בין U ל-V מתפלגות "אחיד".

חלוקה של הגרף ל-k קבוצות תקרא ε-רגולרית אם:

• כל הקבוצות בגודל שווה, או שחלקן גדולות ב-1 (במקרה שמספר הקודקודים ב-G לא מתחלק ב-k)
• כל הזוגות של קבוצות, למעט לכל היותר εk², הם רגולרים.

הלמה

לכל ‎ 0<ε<1 ‎ יש (M=M(ε כך שלכל גרף G קיימת חלוקה ε-רגולרית בגודל לכל היותר M.

רעיון ההוכחה

ההוכחה מתבססת על הגדרת פונקציה q שמקבלת חלוקה ומחזירה מספר בין 1 ל-0. הרעיון בהוכחה הוא להתחיל מהחלוקה הטריוויאלית לחלק אחד, וכל עוד היא לא ε-רגולרית, למצוא חלוקה שמעדנת אותה, כך ש-q גדלה. לשם כך, עבור כל זוג קבוצות שאינן רגולריות, מוצאים שתי תתי קבוצות שהצפיפות שלהן רחוקה מהצפיפות של הקבוצות הגדולות (קיומן של קבוצות כאלו נובע מהגדרת הרגולריות) ולקיחת החלוקה הגסה ביותר כך שכל אחת מתתי הקבוצות האלו יהיו איחוד מחלקות בחלוקה החדשה. אפשר להראות שערך ה-q גדל בלפחות ε⁵, ולפיכך תוך לכל היותר ε^-5 צעדים נגיע לחלוקה שהיא בהכרח רגולרית (כי ערך ה-q לא יכול לעלות מעבר ל-1).

בכל איטרציה, חילקנו את כל אחד מהחלקים למספר חלקים שעלול להיות אקספוננציאלי במספר הקודם (כי לכל חלק אחר מוצאים תת-קבוצה אחרת, והחלוקה שמעדנת את כולן עלולה להיות אקספוננציאלית). מכיוון שיש ε^-5 שלבים בהוכחה, מתקבל חסם שהוא tower-type של ε. בתחילה הייתה תקווה לשפר חסם זה, אך בשנת 1997 הוכיח טימותי גוורס חסם תחתון שגם הוא tower-type, ובכך ביטל תקווה זו.

שימושים

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

הכללות

ללמה יש הכללות רבות, רבות מהן נוגעות להיפרגרף, בדרך כלל k-יוניפורמי (כלומר, שכל קשת חלה בבדיוק k קודקודים; גרף רגיל הוא 2 יוניפורמי). הכללות כאלו ניתנו על ידי גוורס, טרי טאו, נוגה אלון ועוד. בכל ההכללות הללו, החסם המתקבל הוא תמיד השלב ה-k בהיררכית אקרמן (שלב 2 הוא מגדל חזקות).

הכללות נוספות נוגעות לשיפור הדיוק שהגרף המתקבל מקרב את הגרף המקורי.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

25977876למת הרגולריות של סמרדי