Θεωρία Ramsey---------------->Bulletin(1/?)

#1

Ας βάζουμε σε αυτό το θέμα ασκήσεις και θεωρήματα από την θεωρία Ramsey.

Άσκηση 1: Να δειχθεί ότι σε κάθε συνάντηση έξι ατόμων υπάρχουν τρία άτομα που είτε όλοι γνωρίζονται μεταξύ τους είτε όλοι δεν γνωρίζονται μεταξύ τους.

Σε αυτή αλλά και σε επόμενες ασκήσεις θα θεωρούμε (εκτός αν δηλωθεί διαφορετικά) ότι η γνωριμία είναι συμμετρική σχέση. (Δηλαδή αν ο Α γνωρίζει τον Β τότε και ο Β γνωρίζει τον Α)

Ilias_Zad · #2

Βαζω λυση σε αυτην την γνωστη ασκηση.

Ενωνουμε ολα τα ατομα με ακμες(λογω της συμμετρικοτητας τις θεωρουμε μη κατευθυνομενες) τις οποιες και χρωματιζουμε ως εξης,
- Με κοκκινο αν γνωριζονται μεταξυ τους τα δυο αυτα ατομα
- Με πρασινο διαφορετικα.
Οποτε το προβλημα αναγεται στο να δειχτει πως υπαρχει ενα μονοχρωματικο τριγωνο.
Επιλεγουμε ενα τυχαιο ατομο(

). Λογω περιστεροφωλιας υπαρχουν τουλαχιστον 3 ακμες ,που ξεκινουν απο αυτον, και ειναι του ιδιου χρωματος,εστω κοκκινο(πρασινο).Υποθετουμε λοιπον οτι καταληγουν στους b_1,b_2,b_3

.
Συνεπως ο

(δεν) γνωριζετε με τους $b_i,1\leq i \leq 3$ . Aν δυο απο τους b_i

(δεν) γνωριζονται μεταξυ τους (εστω b_k,b_l

) τοτε εχουμε οτι η τριαδα ( a,b_k,b_l

) μας ικανοποιει.
Αν δεν υπαρχει ζευγος που να (μην) γνωριζεται τοτε η τριαδα ( b_1,b_2,b_3

) τωρα μας ικανοποιει οποτε σε καθε περιπτωση ειμαστε οκ

#3

Να σημειώσουμε ότι με παρόμοιο τρόπο λύνεται ένα άλλο πρόβλημα:

Θεωρούμε 6 άρρητους αριθμούς. Να δειχθεί ότι υπάρχουν τρεις ανάμεσα τους τέτοιοι ώστε τα ανά ζεύγη αθροίσματά τους να είναι επίσης άρρητοι αριθμοί.
(http://www.csun.edu/~sf70713/probweek/f ... l03f05.pdf)

Ας συγκριθεί και με το σχετικό viewtopic.php?f=50&t=3288&p=17676#p17676

Φιλικά,

Αχιλλέας

#4

Ωραία. Με την ορολογία που έγραψε ο Ηλίας η άσκηση λέει ότι αν χρωματίσουμε τις ακμές ενός γραφήματος που έχει (τουλάχιστον) έξι κορυφές με δύο χρώματα τότε θα υπάρχει ένα μονοχρωματικό τρίγωνο. Θα δούμε αργότερα ότι για κάθε

αν χρωματίσουμε τις ακμές ενός γραφήματος που έχει αρκετές κορυφές με δύο χρώματα τότε θα υπάρχουν

κορυφές ώστε όλες οι ακμές μεταξύ αυτών των κορυφών να έχουν το ίδιο χρώμα. Ο μικρότερος αριθμός κορυφών για τον οποίο ισχύει το αποτέλεσμα αυτό συμβολίζεται με R(n)

. Έχουμε δηλαδή δείξει ότι $R(3) \leqslant 6$

Άσκηση 1β: Να δειχθεί ότι R(3) = 6

.

Άσκηση 2: Να δειχθεί ότι $R(4) \leqslant 20$ .

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Θα δούμε αργότερα ότι R(4) = 18

.

iosifile · #5

Αποδεικνύεται ότι σε κάθε γράφημα 6 κορυφών υπάρχουν 2 μονοχρωματικά τρίγωνα. Τα τρίγωνα αυτά δεν είναι απαραίτητο να είναι του ιδίου χρώματος.
Λ.Γ.Ιωσηφίδης

Ilias_Zad · #6

Nαι! Το καλοκαιρι στην προετοιμασια το ειχα ακουσει αυτο! Λυνεται με double counting.
Συγκεκριμενα παιρνεις μια τυχαια κορυφη στο K_6

.
Με βαση αυτην θα σχηματιζονται ειτε

ειτε

διχρωματικες γωνιες
( δηλαδη διαφορετικου χρωματος ανα δυο πλευρες που αγονται απο αυτην).

Αρα θα εχουμε συνολικα το πολυ 6*6=36

διχρωματικες γωνιες.
Επειδη ομως τα χρωματα ειναι δυο ακριβως

τετοιες γωνιες αντιστοιχουν σε ενα ακριβως διχρωματικο τριγωνο.

Συνεπως θα εχουμε το πολυ

μη μονοχρωματικα τριγωνα και το λιγοτερο 20 - 18 = 2

μονοχρωματικα

Το οτι το

ειναι ευκολο να δειχτει με αντιπαραδειγμα στο K_5

Το

δεν εχω προλαβει ακομα να το δω

iosifile · #7

Η παραπάνω παρατήρηση μπορεί να γενικεύσει ασκήσεις, όπως αυτήν που πρότεινε ο achilleas.
"Θεωρούμε 6 άρρητους αριθμούς. Να δειχθεί ότι υπάρχουν τρεις ανάμεσα τους τέτοιοι ώστε τα ανά ζεύγη αθροίσματά τους να είναι επίσης άρρητοι αριθμοί"
και να ζητήσουμε να αποδειχτεί ότι υπάρχουν 2 τριάδες αριθμών τέτοιες ώστε....
Τέλος να αναφέρω ότι με βοήθεια Η/Υ υπολογίζεται η πιθανότητα ένα πλήρες γράφημα 6 κορυφών (στο οποίο κάθε ακμή έχει χρωματιστεί με ένα από τα 2 χρώματα) να έχει ακριβώς 2 μονοχρωματικά τρίγωνα είναι 0.0537109.

Λ.Γ.Ιωσηφίδης

#8

Μια άλλη ενδιαφέρουσα σύνδεση του ίδιου προβλήματος είναι με το παιχνίδι SIM

http://en.wikipedia.org/wiki/Sim_(pencil_game)

Δείτε και το Α2 του Putnam 1953.

http://www.mat.itu.edu.tr/gungor/IMO/ww ... utn53.html

Το πρόβλημα ήταν γνωστό και είχε δοθεί ως θέμα και σε προηγούμενους διαγωνισμούς (π.χ. Ουγγαρία, 1947).

Φιλικά,

Αχιλλέας

#9

Ilias_Zad έγραψε:Nαι! Το καλοκαιρι στην προετοιμασια το ειχα ακουσει αυτο! Λυνεται με double counting.
Συγκεκριμενα παιρνεις μια τυχαια κορυφη στο .
Με βαση αυτην θα σχηματιζονται ειτε ειτε ειτε διχρωματικες γωνιες
( δηλαδη διαφορετικου χρωματος ανα δυο πλευρες που αγονται απο αυτην).

Αρα θα εχουμε συνολικα το πολυ διχρωματικες γωνιες.
Επειδη ομως τα χρωματα ειναι δυο ακριβως τετοιες γωνιες αντιστοιχουν σε ενα ακριβως διχρωματικο τριγωνο.

Συνεπως θα εχουμε το πολυ μη μονοχρωματικα τριγωνα και το λιγοτερο μονοχρωματικα

Πολύ όμορφη η λύση του Ηλία. Γενικεύεται μάλιστα για γραφήματα με περισσότερες κορυφές (δείτε την άσκηση 3β). Θα δώσω μια διαφορετική λύση η οποία όμως δεν γενικεύεται:

Γνωρίζουμε ήδη ότι υπάρχει ένα μονοχρωματικό τρίγωνο, έστω μπλε. Παίρνουμε μια κορυφή εκτός του τριγώνου. Θα υπάρχουν τρεις ακμες που προσπίπτουν σε αυτή την κορυφή και έχουν ακριβώς το ίδιο χρώμα. Ακριβώς όπως προηγουμένως θα πάρουμε ένα καινούργιο μονοχρωματικό τρίγωνο εκτός εάν αυτές οι τρεις ακμές ήταν κόκκινες και το μονοχρωματικό τρίγωνο που παίρνουμε είναι μπλε και ταυτίζεται με το παλίο. Επαναλαμβάνοντας με μια καινούργια κορυφή βλέπουμε ότι κάθε ακμή που συνδέει μια κορυφή του τριγώνου με μια άλλη κορυφή που δεν βρίσκεται στο τρίγωνο πρέπει να είναι μπλε. Αλλά τότε όπως και να χρωματίσουμε τις τρεις υπόλοιπες ακμές θα πάρουμε ένα καινούργιο μονοχρωματικό τρίγωνο.

Άσκηση 3α: Χρησιμοποιήστε το αποτέλεσμα της άσκησης 1 για να δείξετε ότι σε κάθε γράφημα με

κορυφές αν οι ακμές χρωματιστούν με δύο χρώματα τότε υπάρχουν τουλάχιστον $\displaystyle{\frac{n(n-1)(n-2)}{120} }$ μονοχρωματικά τρίγωνα.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Άσκηση 3β: Χρησιμοποιήστε την πιο πάνω μέθοδο του Ηλία για να δείξετε ότι σε κάθε γράφημα με

κορυφές αν οι ακμές χρωματιστούν με δύο χρώματα τότε υπάρχουν τουλάχιστον $\displaystyle{\frac{n(n-1)(n-5)}{24} }$ μονοχρωματικά τρίγωνα.

Διόρθωσα την υπόδειξη της άσκησης 3α μετά από προσωπικό μήνυμα του iosifile

#10

iosifile έγραψε: Τέλος να αναφέρω ότι με βοήθεια Η/Υ υπολογίζεται η πιθανότητα ένα πλήρες γράφημα 6 κορυφών (στο οποίο κάθε ακμή έχει χρωματιστεί με ένα από τα 2 χρώματα) να έχει ακριβώς 2 μονοχρωματικά τρίγωνα είναι 0.0537109.

Να αποδειχθεί και χωρίς την βοήθεια υπολογιστή

(Παρατηρήστε ότι από την πιο πάνω απόδειξη του Ηλία κάθε τέτοιο γράφημα θα έχει ακριβώς δύο μονοχρωματικά τρίγωνα αν και μόνο αν σε κάθε κορυφή προσπίπτουν είτε δύο είτε τρεις μπλε ακμές. Δείξτε ότι υπάρχουν ακριβώς 1760 τέτοια γραφήματα. (Θέλει να μελετηθούν αρκετές περιπτώσεις αλλά μπορεί να γίνει και χωρίς υπολογιστή.) Άρα η πιθανότητα ισούται με $\displaystyle{ \frac{1760}{2^{15}} = \frac{55}{1024} = 0.0537109375 }$ . (Για την τελευταία ισότητα χρησιμοποίησα υπολογιστική αν και με λίγη υπομονή βγαίνει και χωρίς υπολογιστική.)

Ilias_Zad · #11

Καλημερα σας.
Αρχικα Δημητρη ειναι οντως ωραια η λυση με τις μονοχρωματικες γωνιες αλλα θελω να τονισω οτι δεν ειναι δικια μου. Στην προετοιμασια ειχα ακουσει την ασκηση με την λυση της. Το λεω γιατι δεν μου αρεσει να επιβραβευομαι για οχι δικα μου πραγματα.

Βαζω λυση μου ομως τωρα για την ασκηση 2.

Αρχικα θα αποδειξω την υποδειξη-λημμα που αναφερεις.
Στο $K_{10}$ διαλεγουμε μια τυχαια κορυφη, εστω

, και παιρνουμε

περιπτωσεις.

Αν υπαρχουν

κοκκινες ακμες που αγονται απο αυτην και πανε στις κορυφες u_1,u_2,u_3,u_4

αντιστοιχα,
τοτε ειτε θα υπαρχει μια κοκκινη ακμη στην μεταξυ τους συνδεση και θα σχηματιζοταν κοκκινο τριγωνο μαζι με την

,

ειτε θα ειναι ολες oι ακμες που τις συνδεουν μεταξυ τους χρωματος μπλε και θα σχηματιζοταν ενα μπλε K_4

.

Απο την αλλη ομως αν δεν υπαρχει τετραδα κοκκινων ακμων που αγονται απο την

τοτε αναγκαστικα θα εχουμε μια εξαδα μπλε (που θα πηγαινουν στις w_i

)

Τοτε ομως εχουμε K_6

με κορυφες τις w_i

αρα θα υπαρχει ειτε ενα κοκκινο τριγωνο ειτε ενα μπλε K_4

(αφου συνδεονται με μπλε μαζι με την a)

Συνεπως εχουμε δειξει οτι χρωματιζοντας ενα $K_{10}$ με μπλε και κοκκινο εχουμε ειτε ενα K_4

μπλε ειτε ενα κοκκινο τριγωνο. (ή αναποδα)

Τωρα πισω στην ασκηση μας οπου τα πραγματα πια ειναι αρκετα απλα.

Διαλεγουμε μια κορυφη , εστω

, και τις

ιδιου χρωματος , wlog κοκκινες, ακμες που αγονται απο αυτην. Απο το λημμα σε αυτο το $K_{10}$ υπαρχει ειτε ενα K_4

μπλε ειτε ενα κοκκινο τριγωνο που μαζι με την

μας δινουν ενα κοκκινο K_4

. and qed!

#12

Πολύ ωραία. Ας γράψουμε R(m,n)

για το μικρότερο αριθμό ώστε όπως και αν χρωματίσουμε τις ακμές ενός γραφήματος με τόσες κορυφές μπλε και κόκκινο τότε είτε θα υπάρχει ένα μπλε K_m

, είτε θα υπάρχει ένα κόκκινο Κ_n

. Με αυτήν την ορολογία R(n) = R(n,n)

και

.

Δείξαμε μέχρι στιγμής ότι $R(3,3)=6,R(3,4) \leqslant 10$ και $R(4,4) \leqslant 20$ . Είναι επίσης προφανές ότι για κάθε $n \geqslant 2$ έχουμε R(n,2) = n

Άσκηση 4: Να δείξετε ότι $R(m,n) \leqslant R(m-1,n) + R(n,m-1)$

Επαγωγικά τώρα μπορούμε να συμπεράνουμε ότι

Θεώρημα Ramsey (Για γραφήματα με δύο χρώματα): Για κάθε

, όπως και να χρωματίσουμε τις ακμές ενός γραφήματος που έχει αρκετές κορυφές με δύο χρώματα, τότε θα υπάρχει ένα μονοχρωματικό K_n

Η αρχική απόδειξη του Ramsey έδινε $R(n) \leqslant n!$ . Χρησιμοποιώντας την άσκηση 4 και επαγωγή στο k=m+n

μπορούμε να συμπεράνουμε ότι $R(m,n) \leqslant 2^{m+n}$ και άρα $R(n) \leqslant 4^n$ . Με λίγη περισσότερη προσοχή μπορούμε να δώσουμε ένα λίγο καλύτερο φράγμα:

Θεώρημα (Erdos-Szekeres): $\displaystyle{ R(m,n) \leqslant \binom{m+n-2}{m-1}}$ για κάθε $m,n\geqslant 2$

Απόδειξη: Μπορούμε να υποθέσουμε ότι $m,n \geqslant 3$ . (Έχουμε ήδη παρατηρήσει ότι R(m,2) = R(2,m) = m

.) Χρησιμοποιούμε επαγωγή στο k=m+n

. Από την επαγωγική υπόθεση μπορούμε να υποθέσουμε ότι $\displaystyle{ R(m-1,n) \leqslant \binom{m+n-3}{m-2}}$ και $\displaystyle{ R(m,n-1) \leqslant \binom{m+n-3}{n-2}}$ . Άρα από την άσκηση 4 συμπεραίνουμε ότι $\displaystyle{ R(m,n) \leqslant \binom{m+n-3}{m-2} + \binom{m+n-3}{n-2} = \binom{m+n-2}{m-1} }$

Γενικά οι αριθμοί Ramsey είναι εξαιρετικά δύσκολο να υπολογιστούν. Για παράδειγμα είναι άγνωστη η τιμή του R(5)

. (Έχει αποδειχθεί με χρήση υπολογιστών ότι $43 \leqslant R(5) \leqslant 49$ .) Για παράδειγμα μια αφελής προσπάθεια για να δείξουμε ότι $R(5) \leqslant 48$ θα ήταν να ελέγξουμε όλους τους χρωματισμούς με δύο χρώματα του $K_{48}$ . Υπάρχουν όμως $\displaystyle{2^{\binom{48}{2}} = 2^{1128} > 10^{338}}$ διαφορετικοί χρωματισμοί και ο έλεγχος ακόμη και με χρήση υπολογιστή είναι αδύνατος.

Πρόσθεσα ότι το θεώρημα μιλάει για δύο χρώματα. Για περισσότερα χρώματα δείτε πιο κάτω.

Ilias_Zad · #13

Καλησπερα!
H ασκηση 4 που εβαλες Δημητρη πριν λιγο διαπιστωσα πως αντιμετωπιζεται αρκετα ευκολα με τον τροπο που αντιμετωπισα το $K_{20}$ !
Δηλαδη παιρνεις ειτε τις R(p,q-1)

κοκκινες ακμες ειτε τις R(q-1,p)

μπλε και πας οπως παραπανω διακρινωντας λιγες περιπτωσεις.
Για το $R(4) \leq 18$ τωρα αρκει να δειξουμε οτι R(3,4)=9.

Ομως η αντιμετωπιση τωρα ειναι ιδια με την πιο πανω του $K_{10}$ με την παρατηρηση του οτι μπορουμε να βρουμε παντα τουλαχιστον μια κορυφη με ειτε 4 κοκκινες ακμες ειτε 6 μπλε. Αυτο γιατι σε διαφορετικη περιπτωση θα ειχαμε σε καθε μια κορυφη να αντιστοιχουν 3 κοκκινες και 5 μπλε και βγαζοντας πχ τις κοκκινες ακμες ενος χρωματος θα ειχαμε γραφο με $\sum deg(v_i)=5*9=45 \equiv 1 (mod2)$ κατι προφανως ατοπο!

#14

Ilias_Zad έγραψε:Καλησπερα!
H ασκηση 4 που εβαλες Δημητρη πριν λιγο διαπιστωσα πως αντιμετωπιζεται αρκετα ευκολα με τον τροπο που αντιμετωπισα το $K_{20}$ !
Δηλαδη παιρνεις ειτε τις κοκκινες ακμες ειτε τις μπλε και πας οπως παραπανω διακρινωντας λιγες περιπτωσεις.
Για το $R(4) \leq 18$ τωρα αρκει να δειξουμε οτι $R(3,4) {\color{red} \leqslant}9.$ Ομως η αντιμετωπιση τωρα ειναι ιδια με την πιο πανω του $K_{10}$ με την παρατηρηση του οτι μπορουμε να βρουμε παντα τουλαχιστον μια κορυφη με ειτε 4 κοκκινες ακμες ειτε 6 μπλε. Αυτο γιατι σε διαφορετικη περιπτωση θα ειχαμε σε καθε μια κορυφη να αντιστοιχουν 3 κοκκινες και 5 μπλε και βγαζοντας πχ τις κοκκινες ακμες ενος χρωματος θα ειχαμε γραφο με $\sum deg(v_i)=5*9=45 \equiv 1 (mod2)$ κατι προφανως ατοπο!

Πολύ ωραία. (Έκανα μια μικρή διόρθωση.) Η μέθοδος αυτή δείχνει πως μερικές φορές μπορούμε να βελτιώσουμε το αποτέλεσμα της άσκησης 4. Πιο συγκεκριμένα, αν R(m-1,n)

και

είναι και οι δύο άρτιοι τότε $R(m,n) \leqslant R(m-1,n) + R(m,n-1) - 1$ .

Άσκηση 5 (IMO 1964/3): Δεκαεφτά άτομα αλληλογραφούν μεταξύ τους. (Δεν υπήρχανε e-mail τότε.

) Στα γράμματα διαπραγματεύονται τρία διαφορετικά θέματα με κάθε ζεύγος ατόμων να διαπραγματεύεται ακριβώς ένα από αυτά. Να δειχθεί ότι υπάρχουν τουλάχιστον τρία άτομα που στις μεταξύ τους αλληλογραφίες διαπραγματεύονται το ίδιο ακριβώς θέμα.

Άσκηση 6 : Δίνονται 18 σημεία στον χώρο ώστε να μην υπάρχουν 4 από αυτά που να ανήκουν στο ίδιο επίπεδο και ώστε όλες οι αποστάσεις που ορίζουν να είναι διαφορετικές. Να δειχθεί ότι υπάρχει τετράεδρο ώστε κάθε ακμή του να είναι η ακμή με το μεγαλύτερο μήκος σε ένα από τα τετράεδρα που σχηματίζουν αυτά τα σημεία.

Άσκηση 7: Να δειχθεί ότι R(4,4) = 18

.

Για την άσκηση 7 πρέπει να κατασκευάσουμε ένα γράφημα με 17 κορυφές και να χρωματίσουμε τις ακμές του κόκκινες/μπλε ώστε να μην υπάρχουν μονοχρωματικά K_4

. Γενικά όπως είπα και πιο πάνω δεν υπάρχει κάποια μεθοδολογία για να το κάνουμε αυτό. Η υπόδειξη που ακολουθεί ευκολύνει κατά πολύ την άσκηση αφού δίνω τον ζητούμενο χρωματισμό και απομένει να ελεγχθεί ότι δουλεύει.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Ilias_Zad · #15

Ασκηση 5.
Ουσιαστικα απλα λογω περιστεροφωλιας εχουμε 6 ακμες απο μια τυχαια κορυφη ιδιου χρωματος, εστω μπλε. Αν καποια ακμη μεταξυ αυτων ειναι μπλε τελος. Αλλιως εχουμε ενα διχρωματικο K_6

και απο ασκηση 1 παλι τελος

Aυτη η ασκηση ισως να δειχνει ποσο εχει αλλαξει η δυσκολια των τοτε IMO με των τωρινων.
ΥΓ Δημητρη απο μενα πραγματικα μπραβο για αυτην σου την συνεισφορα αφου με αρχικα απλες ασκησεις διδασκεις ουσιαστικα τετοιες μεγαλες θεωριες!

#16

Ilias_Zad έγραψε: Aυτη η ασκηση ισως να δειχνει ποσο εχει αλλαξει η δυσκολια των τοτε IMO με των τωρινων.

Πράγματι. Καμία σχέση μεταξύ των παλιών θεμάτων και των τωρινών.

Ilias_Zad έγραψε: ΥΓ Δημητρη απο μενα πραγματικα μπραβο για αυτην σου την συνεισφορα αφου με αρχικα απλες ασκησεις διδασκεις ουσιαστικα τετοιες μεγαλες θεωριες!

Σε εσένα αξίζουν τα μπράβο. Έχω ακόμη αρκετές ασκήσεις να προσθέσω αρκεί κάποιος (λέγε με Ηλία) να συνεχίζει να απαντά.

Dimitris X · #17

Όταν θα αρχίσω να διαβάζω σοβαρά συνδιαστική (από του χρόνου αν είμαστε καλά) μάλλον θα πάρω όλα τα posts σου Δημήτρη και θα τα διαβάζω ένα-ένα...

Σε ευχαριστώ και εγώ για την πολύτημη συνεισφορά σου.....

#18

Η άσκηση 5 λέει το εξής: Όπως και να χρωματίσουμε τις ακμές του $K_{17}$ με τρία χρώματα πάντα θα υπάρχει ένα μονοχρωματικό τρίγωνο.

Θεώρημα Ramsey (Για γραφήματα με πολλαπλά χρώματα) Για κάθε

και κάθε

όπως και να χρωματίσουμε τις ακμές ενός γραφήματος που έχει αρκετές κορυφές με

χρώματα πάντα θα υπάρχει ένα μονοχρωματικό K_n

.

Ο μικρότερος αριθμός κορυφών για τον οποίο ισχύει το θεώρημα συμβολίζεται με R_k(n)

. (Άρα

.) Όπως ορίσαμε τους "ασύμμετρους" αριθμούς R(m,n)

μπορούμε να ορίσουμε και τον αριθμό $R(n_1,n_2,\ldots,n_k)$ ώς τον μικρότερο αριθμό κορυφών που πρέπει να έχει ένα γράφημα ώστε όπως και να χρωματίσουμε τις ακμές του με

χρώματα να περιέχει είτε ένα $K_{n_1}$ χρωματισμένο με το πρώτο χρώμα, είτε ένα $K_{n_2}$ χρωματισμένο με το δεύτερο χρώμα είτε ... είτε ένα $K_{n_k}$ χρωματισμένο με το

-οστό χρώμα.

Οι παρακάτω ασκήσεις δίνουν δυο διαφορετικές αποδείξεις του θεωρήματος Ramsey για πολλά χρώματα.

Άσκηση 8α: Να δείξετε ότι $\displaystyle{R(n_1,\ldots,n_k) \leqslant R(n_1-1,\ldots,n_k) + R(n_1,n_2-1,\ldots,n_k) + \cdots + R(n_1,\ldots,n_k-1) - k + 2}$

Άσκηση 8β: (Αν $k \geqslant 3$ ) Να δείξετε ότι $\displaystyle{R(n_1,\ldots,n_k) \leqslant R(n_1,\ldots,n_{k-2},R(n_{k-1},n_k))}$

Μάκης Χατζόπουλος · #19

Βρήκα κάποιες σημειώσεις πάνω στην θεωρία του Ramsey, επειδή το αγνοούσα το θεώρημα και τις μοιράζομαι μαζί σας!! Αν έχετε σημειώσεις πάνω στο θέμα (κατατοπιστικές με θεωρία και λυμένες ασκήσεις) θα ήταν ευπρόσδεκτες!

#20

Demetres έγραψε: Άσκηση 8α: Να δείξετε ότι $\displaystyle{R(n_1,\ldots,n_k) \leqslant R(n_1-1,\ldots,n_k) + R(n_1,n_2-1,\ldots,n_k) + \cdots + R(n_1,\ldots,n_k-1) - k + 2}$

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Demetres έγραψε: Άσκηση 8β: (Αν $k \geqslant 3$ ) Να δείξετε ότι $\displaystyle{R(n_1,\ldots,n_k) \leqslant R(n_1,\ldots,n_{k-2},R(n_{k-1},n_k))}$

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Θεωρία Ramsey---------------->Bulletin(1/?)

Θεωρία Ramsey---------------->Bulletin(1/?)

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Μέλη σε σύνδεση