שאלה מאד בסיסית לגבי רמזי

[student47]

שאלה מאד בסיסית לגבי רמזי

אם יש לי גרף מלא עם 5 קדקדים ואני צובע את צלעותיו כרצוני בכחול ואדום. אז לא מובטח לי שיש בו K3 כחול או K3 אדום.

הצלחתי לצייר גרף מלא עם 5 קדקדים, 5 צלעות כחולות, 5 צלעות אדומות כך שאין משולש אדום ואין משולש כחול.

למה זה אומר שבפרט אם אקח גרף מלא עם מספר קדקדים < 5, אין סיכוי שיהיה בו משולש כחול או משולש אדום?

נראה לי משהו טריוויאלי אבל אני לא יודע ממש להסביר את זה..

 

[אורי769]

פשוט מאד

נניח יש לך גרף מלא על 4 קודקודים. אז תוסיף לו קודקוד חמישי בשם x, כולל צלעות לכל שאר הקודקודים.... תצבע בצביעה שלא מקיימת תנאי רמזי 3,3... תסיר את קודקוד x, כולל כל הצלעות שיוצאות ממנו.... קיבלתי צביעה של K4 שלא מקיימת תנאי רמזי 3,3.

 

[student47]

תודה. ועוד משהו ספציפי לגבי רמזי ששאלתי ולא מובן לי.

האמת לא אתה ענית לי על זה..מישהו אחר ענה ולי זה לא היה ממש מובן.

מדובר על ההוכחה בעמ' 2, עד ממש תחילת עמוד 3 של משפט רמזי.

מה שלא מובן לי זה 3 דברים:

1. בסוף ההוכחה בתחילת עמוד 3 כתוב שהתת גרף H של G המושרה ע"י שכני u (כלומר שקדקדיו הם שכני u, וצלעותיו הם הצלעות שבין שכני u), הוא לפחות מסדר zz R(s-1,t) zz (זה בגלל שהדרגה של u היא לפחות (R(s-1,t.
כעת, מה שלא ברור לי, זה למה H מכיל תת גרף איזומורפי ל-Ks-1 או שהמשלים שלו מכיל תת גרף איזומורפי ל-Kt.
הרי זה שבגרף כלשהו יש x קדקדים (ובמקרה הזה (x = R(s-1,t ), למה זה מבטיח שהוא מכיל תת גרף איזומורפי ל-Ks-1 או שהמשלים שלו מכיל
תת גרף איזומורפי ל-Kt?

2. בשורה האחרונה בהוכחה כתוב: "אם H מכיל את Ks-1 אז יחד עם u הוא מכיל את Ks". עתה, יש לציין ש-G מכיל את Ks, לא?

3. אם התשובה ל-2 היא כן, אז בסך הכל מה שעשו פה, זה לקחו תת גרף H של G שמושרה ע"י שכני u.
והגיעו למסקנה ש-G מכיל את Ks או ש-G מכיל את Kt.
למה מפה מגיעים לכך ש-R(s,t)<=R(s-1,t)+R(s,t-1), ולכך ש-R(s,t)<infinity?

תודה מראש ושנה טובה !

 

[student47]

כאן הלינק להוכחה שעליה אני שואל. שכחתי לצרפו

http://math-wiki.com/images/3/3c/GT.L11.pdf

 

[student47]

התשובהלשאלה1 שלי נובעת אך ורק, ובאופן מיידי מהגדרת מס' רמזי?

כי אני בטוח כבר שההגדרה די ברורה לי, אבל כאן אני חושב שיש איזה דקות או משהו שאני לא מבין...אני די בטוח שהתשובה לא נובעת אך ורק, ובאופן מיידי
מההגדרה.
הרי מה שאמרו שם, זה שאם הסדר של גרף הוא לפחות R(s-1,t), אז אני יכול להגיד שהוא מכיל תת גרף איזו' ל-Ks-1 או שמשלימו מכיל תת גרף איזו'
ל-Kt.

אבל זו לא ההגדרה של מס' רמזי.
ההגדרה אומרת, שמס' רמזי R(s,t) הוא המספר הטבעי המינימלי n כך שלכל גרף פשוט G מסדר n מתקיים...".
במשפט, הם לקחו גרף כלשהו ואמרו שהסדר שלו הוא מספר הגדול שווה ממספר כלשהו שהם סימנו אותו ב-R(s-1,t).

לא יודע אם הצלחתי להסביר את האי הבנה אצלי כמו שצריך..

 

[אורי769]

הסבר

נכון שההגדרה היא ש-(R(s,t זה המספר המינימלי x שלכל גרף על x קודקודים יש Ks או שבמשלימו יש Kt. הנקודה שכל גרף על יותר קודקודים ודאי מקיים את התנאי הזה. לכן ניתן לומר "לפחות (R(s,t"

 

[student47]

תגובה

כן...האמת שה"לפחות" זו לא הנקודה שהפריעה לי..למרות שבאמת צריך לתת עליה את הדעת..ואני מבין מה שענית לי.

בכל אופן, אתה אומר אז שהמעבר שם נובע רק מההגדרה של רמזי כן? כלומר אם בהינתן גרף שהסדר שלו הוא R(s-1,t)
(או לפחות R(s-1,t)), אזי הוא מכיל תת גרף איזו ל-Ks, או תת גרף איזו' ל-Kt?

אגב..אם תוכל בקשה לנסות לענות לי על שאלות 2,3. זה מה שחסר לי על מנת להגיע להבנה של ההוכחה.

 

[אורי769]

צריך לדייק

מה שאתה כותב אינה ההגדרה: בהנתן גרף שהסדר שלו לפחות (R(s-1,t אזי הוא מכיל תת גרף איזומורפי ל-(K(s-1 או שהמשלים שלו מכיל תת גרף איזו' ל-Kt.

התשובה לשאלה 2 שלך היא כן. התשובה לשאלה 3 היא שזה שוב נובע מהגדרת מספר רמזי: לקחנו גרף על (R(s-1,t) + R(s,t-1 קודקודים והוכחנו שהוא מקיים את תנאי רמזי ל-s,t. מה זה אומר על (R(s,t?

 

[student47]

ניסיון תשובה

ההגדרה אומרת ש- (R(s,t הוא המספר הטבעי המינימלי כך שכך גרף פשוט G מסדר (R(s,t מקיים:
G מכיל תת גרף איזו' ל-Ks או G משלים מכיל תת גרף איזו' ל-Kt.

כאן יש לי גרף G שהסדר שלו אינו (R(s,t , אלא: (R(s-1,t) + R(s,t-1.
ו-G מכיל תת גרף איזומורפי ל-Ks או שהמשלים של G מכיל תת גרף איזומורפי ל-Kt.

איך זה נובע מההגדרה? איך אני מפעיל את ההגדרה על גרף שהוא לא מסדר (R(s,t, אבל מכיל תת גרף איזו' ל-Ks או שמשלימו מכיל תת גרף איזו ל-Kt?

 

[אורי769]

שאלה

נניח אני מנסה לחשב את (R(8,8. נניח הוכחתי שלכל גרף בעל 1000 קודקודים מקיים שהוא מכיל K8 או שמשלימו מכיל K8. מה זה אומר על (R(8,8?

 

[student47]

זה אומר ש-(R(8,8 קטן או שווה ל-1000, לא?

 

[אורי769]

נכון

עכשיו, במקום 1000 תגיד R(s-1,t)+R(s,t-1) q ובמקום (R(8,8 תגיד (R(s,t.

 

[student47]

תודה רבה לך על התשובות והעזרה