משפט ארדש-סקרש

במתמטיקה דיסקרטית, משפט ארדש–סקרש הוא משפט הקובע, שלכל $a,b$ טבעיים, בכל סדרה באורך $\ ab+1$ של מספרים ממשיים שונים יש תת־סדרה עולה באורך $\ a+1$ או תת־סדרה יורדת באורך $\ b+1$. זהו משפט טיפוסי בתורת רמזי – במבנה גדול דיו אי־אפשר להימנע ממידה מסוימת של סדר.

את המשפט הוכיחו פאול ארדש וגאורגה סקרש, במאמר שפרסמו בשנת 1935.

המשפט

יהיו $a,b$ מספרים טבעיים, ותהי $\ x_{1},x_{2},...,x_{ab+1}$ סדרה של מספרים ממשיים שונים. אזי יש תת־סדרה מונוטונית עולה ממש באורך $\ a+1$, או שיש תת־סדרה מונוטונית יורדת ממש באורך $\ b+1$.

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

הוכחת המשפט

הוכחה ראשונה

נגדיר לכל $\ i$ את $\ u_{i}$ להיות אורך תת־הסדרה העולה הארוכה ביותר המתחילה ב$\ x_{i}$, ובאופן דומה את $\ d_{i}$ להיות אורך תת־הסדרה היורדת הארוכה ביותר המתחילה ב$\ x_{i}$.

למה: אם $\ u_{i}=u_{j}$ עבור $\ i<j$, אז $\ x_{i}>x_{j}$. באופן דומה אם $\ d_{i}=d_{j}$ עבור $\ i<j$ כך $\ x_{i}<x_{j}$.

הוכחה: אם $\ u_{i}=u_{j}$ ו$\ x_{i}<x_{j}$, אז לכל תת־סדרה עולה שמתחילה ב־$\ x_{j}$ ניתן לצרף בתחילתה את $\ x_{i}$ ולקבל תת־סדרה עולה ארוכה יותר. מכאן $\ u_{i}>u_{j}$, בסתירה לנתון. באופן דומה ניתן לקבל את הלמה על $d_{i}$ ו- $\ d_{j}$.

כעת נעבור להוכחת המשפט עצמו. נניח בשלילה כי אין מוצאים תת־סדרה עולה ממש באורך $\ a+1$ ואין תת־סדרה יורדת ממש באורך $\ b+1$. לכן, לכל $\ i$ מתקיים $\ u_{i}\leq a$. כמו־כן, $\ d_{i}\leq b$; אי־לכך, יש רק $\ ab$ אפשרויות לערכי הזוג הסדור $\ (u_{i},d_{i})$. לעומת זאת, יש $\ ab+1$ זוגות כנ"ל: $\ (u_{1},d_{1}),(u_{2},d_{2}),...,(u_{ab+1},d_{ab+1})$.

מעקרון שובך היונים קיימים $\ 1\leq i<j\leq ab+1$ כך ש־$\ (u_{i},d_{i})=(u_{j},d_{j})$. כלומר, $\ u_{i}=u_{j}$ וכן $\ d_{i}=d_{j}$. על־כן, מהלמה $\ x_{i}>x_{j}$ וגם $\ x_{i}<x_{j}$; סתירה.

הוכחה שנייה

לכל מספר $x_{i}$ נבחר את $n_{i}$ להיות אורך הסדרה היורדת הארוכה ביותר המתחילה ב$x_{i}$. אם אחד מאיברי הסדרה $\left\{n_{i}\right\}$ גדול מ-$b$, תת־הסדרה המתאימה לו היא תת־סדרה יורדת מאורך גדול מ־$b+1$. וָלא, על פי עקרון דיריכלה יש לפחות $\left\lceil {\frac {ab+1}{b}}\right\rceil =\left\lceil a+{\frac {1}{b}}\right\rceil =a+1$ איברים בסדרה $\left\{n_{i}\right\}$ השווים זה־לזה, נסמן את תת־הסדרה המתאימה להם ב־$\left\{n_{i_{k}}\right\}$ ואת ערכם המשותף ב־$m$. נשים לב ש־$x_{i_{1}}$ בהכרח קטן מ־$x_{i_{2}}$ (אחרת – היה אפשר לקחת את הסדרה המתחילה ב־$x_{i_{1}}$, לאחריו $x_{i_{2}}$ ולאחר מכן, את הסדרה באורך $m$ המתחילה ב־$x_{i_{2}}$, ובכך למצוא סדרה יורדת המתחילה ב־$x_{i_{1}}$, בעלת אורך גדול מ־$m$). אותו נימוק תקף לכל $a+1$ האיברים, לפיכך, אם ניקח אותם נקבל סדרה עולה כמבוקש.

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

הוכחה שהחסם הדוק

יהיו $a,b$ מספרים טבעיים. נתבונן בסדרה הבאה:

$b,b-1,\dots ,1,2b,2b-1,\dots ,b+1,3b,\dots ,\dots ,ab,ab-1,\dots ,ab-b+1$

נשים לב שהסדרה מכילה את כל המספרים מ־1 ועד $ab$, ולכן יש בה בדיוק $ab$ איברים. כמו־כן, נשים לב שאחרי כל איבר יש לכל היותר $b-1$ איברים קטנים ממנו, ובפרט, סדרה יורדת מקסימלית היא באורך $b$ לכל היותר. בנוסף, אם נחלק את הסדרה ל־$a$ תת־סדרות באורך $b$ – אז עבור כל איבר – האיבר הבא אחריו, שגדול ממנו, חייב להימצא בתת־הסדרה הבאה. לכן, תת־סדרה עולה מקסימלית היא באורך $a$. מכאן, אין קיימת לסדרה זו תת־סדרה יורדת באורך $b+1$, ובנסוף, אין לה תת־סדרה עולה באורך $a+1$. בשל כך, אין משפט ארדש–סקרש מתקיים עבור סדרות באורך $ab$.

ראו גם

• תורת רמזי

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

• משפט ארדש-סקרש, באתר MathWorld (באנגלית)

• Erdős, Paul; Szekeres, George (1935). "A combinatorial problem in geometry", Compositio Mathematica 2: 463–470.