משפט מנטל

משפט מנטל בתורת הגרפים הוא משפט הקובע כי בהינתן גרף פשוט לא מכוון עם n צמתים וחסר משולשים (חסר מעגלים באורך 3), אז מספר הקשתות שלו הוא לכל היותר $\lfloor \frac{n^2}{4}\rfloor$. החסם אותו נותן משפט מנטל הוא הדוק שכן הגרף הדו-צדדי המלא ($K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$) הוא חסר משולשים וכן מספר הקשתות שלו הוא $\lfloor \frac{n^2}{4}\rfloor$.

לפי השקילות הלוגית $\alpha ⟹\beta \equiv ⌝\beta ⟹⌝\alpha$ נוכל לקבל ניסוח שקול למשפט הטוען כי אם בגרף G פשוט ולא מכוון יש יותר מ$\lfloor \frac{n^2}{4}\rfloor$ קשתות אז יש ב-G משולש.

משפט מנטל הוא מקרה פרטי של משפט טורן.

הגדרה פורמלית

יהי $G=<V,E>$ גרף, נסמן $|V|=n$, נניח כי לכל 3 צמתים $v_1,v_2,v_3\in V$ שונים בגרף, מתקיים $⌝(\{v_1,v_2\}\in E\wedge \{v_2,v_3\}\in E\wedge \{v_1,v_3\}\in E)$, אז $|E|\le \lfloor \frac{n^2}{4}\rfloor$

הוכחות

הוכחה 1

יהי $G=<V,E>$ גרף חסר משולשים. נבנה ממנו גרף דו-צדדי $G^{\prime }=<V,E^{\prime }>$ כך ש$|E|\le |E^{\prime }|\le \lfloor \frac{n^2}{4}\rfloor$, מה שיוכיח את המשפט, שכן גרף הוא דו צדדי אמ“ם אין בו מעגלים מאורך אי-זוגי, ובפרט באורך 3.

נסמן $v\in V$ הצומת בעל הדרגה המקסימלית. כמו כן, נסמן ב$S$ את $\{u\in V|\{v,u\}\in E\}$ (קבוצת השכנים). כעת נביט בגרף הדו-צדדי המלא $G^{\prime }=<V,E^{\prime }>$ על S ועל $V\setminus S$, נוכיח כעת כי $\mathrm{\forall }w\in V.de{g}_G(w)\le de{g}_{G^{\prime }}(w)$, ומנוסחת לחיצות היידים, נוכל להסיק כי $|E|\le |E^{\prime }|$, וזה יסיים את ההוכחה.

יהי $w\in V$, נחלק למקרים:

אם $w\notin S$, אז $de{g}_{G^{\prime }}(w)=|S|\ge de{g}_G(w)$ שכן $|S|$ היא הדרגה המקסימלית בגרף G, לפי הגדרת S.

אם $w\in S$, אז $de{g}_{G^{\prime }}(w)=|V\setminus S|\ge de{g}_G(w)$ מפני שגם בגרף G לא היו קשתות בין קודקודים S כיוון ש-G חסר משולשים (אם הייתה קשת בין $u_1,u_2\in S$ אז$v-u_1-u_2-v$ משולש ב-G). כמו כן $|E^{\prime }|\le \lfloor \frac{n^2}{4}\rfloor$ מפני שהמקרה גרוע ביותר הוא כאשר $|S|=\lfloor \frac{n}{2}\rfloor \wedge |V\setminus S|=\lceil \frac{n}{2}\rceil$ (שטח ריבוע הוא מקסימלי)

הוכחה 2 (weight shifting)

יהי $G=<V,E>$ גרף חסר משולשים. נגדיר פונקציית מטרה $$f(G)=\underset{0\le x_i\le 1}{\max }\sum _{(i,j)\in E}{x}_i\cdot x_j$$ כאשר $\sum _{i=1}^n{x}_i=1$

אפשר לחשוב על זה כמו מתן משקלים לכל צומת, והמשקל של כל קשת הוא $x_i\cdot x_j$

נבחין כי אם השמת משקולות כלשהי מקבלת ערך מקסימלי, אז קיימת השמת משקולות אחרת בה מתקיים שאם $x_i,x_j>0$ אז יש קשת בין $x_i,x_j$.

אכן, תהא השמה כזאת, ונניח שאין קשת בין $x_i,x_j$. נסמן ב$N(x)$ את סכום המשקלים של השכנים של $x$. בה"כ מתקיים ש $N(x_1)\ge N(x_2)$, ולכן השמת המשקולות שתיתן לכל צומת את אותו המשקל כמו ההשמה המקורית, פרט ל$x_i=x_i+x_j$ ול$x_j=0$ היא השמה חוקית שמקבלת ערך לפחות כמו ההשמה הקודמת.

נוכל להמשיך כך באידנקוציה עד שנקבל את הטענה הרצויה.

לכן, מתקיים כי $f(G)\le \frac{1}{4}$ שכן אין ב$G$ משולשים ולכן הקליקה הגדולה ביותר בו היא מגודל 2, ובפרט השמת משקולות חוקית כך שאם $x_i,x_j>0$ אז יש קשת בין $x_i,x_j$נותנת משקל חיובי לשני צמתים לכל היותר, והמקסימום של מכפלת שני ערכים חיוביים שסכומם 1 הוא $\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$.

מצד שני, אם ניתן את ההשמה $x_i=\frac{1}{n}$ לכל הצמתים, נקבל כי $$\frac{m}{n^2}=\sum _{(i,j)\in E}{x}_i\cdot x_j=\sum _{(i,j)\in E}\frac{1}{n^2}\le f(G)\le \frac{1}{4}$$ועל ידי העברת אגפים נקבל את אי השוויון הרצוי.

הערות שוליים

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

משפט מנטל41176381Q117679663