«Σε μια αρκετά μεγάλη τάξη, το πλήρες χάος είναι αδύνατο» — Φρ. Ράμσεϊ
1) Το «πρόβλημα του πάρτι» και ο ορισμός
Σε ένα πάρτι χρωματίζουμε την ακμή ανάμεσα σε δύο άτομα κόκκινη αν γνωρίζονται και μπλε αν δεν γνωρίζονται. Το ερώτημα: πόσοι χρειάζονται ώστε να είμαστε σίγουροι πως υπάρχει είτε κόκκινο τρίγωνο (τρεις όλοι γνωστοί) είτε μπλε τρίγωνο (τρεις όλοι άγνωστοι);
Γενικά, ορίζουμε τον αριθμό Ramsey R(s,t) ως το ελάχιστο n ώστε κάθε δίχρωμος χρωματισμός των ακμών του πλήρους γράφου K_n (όπου κάθε ζευγάρι κορυφών συνδέεται με ακμή) περιέχει είτε κόκκινο K_s είτε μπλε K_t.
Για s=t γράφουμε R(s)=R(s,s).
2) Θεμελιώδες παράδειγμα: R(3)=6
(α) Κάτω φράγμα: R(3) > 5
Υπάρχει δίχρωμος χρωματισμός του K_5 χωρίς μονόχρωμο τρίγωνο. Για παράδειγμα, σχηματίζουμε έναν κύκλο 5 κορυφών και χρωματίζουμε τις ακμές του κύκλου κόκκινες και τις διαγωνίους μπλε (ή αντίστροφα). Άρα R(3) ≥ 6.
(β) Άνω φράγμα: R(3) ≤ 6
Πάρε οποιονδήποτε δίχρωμο χρωματισμό του K_6 και διάλεξε μια κορυφή v. Έχει 5 ακμές που φεύγουν από αυτήν· με την αρχή του περιστερεώνα τουλάχιστον 3 είναι του ίδιου χρώματος, έστω κόκκινες προς κορυφές a,b,c.
Αν κάποια ακμή μεταξύ a,b,c είναι κόκκινη, με τη v σχηματίζεται κόκκινο τρίγωνο. Αν όλες ab, bc, ca είναι μπλε, έχουμε μπλε τρίγωνο.
Άρα κάθε δίχρωμος χρωματισμός του K_6 περιέχει μονόχρωμο τρίγωνο. Συνεπώς R(3)=6.
3) Η σχέση Erdős–Szekeres (1935)
Για s,t ≥ 3 ισχύει:
R(s,t) ≤ R(s-1,t) + R(s,t-1)
Ιδέα απόδειξης
Θέτουμε n = R(s-1,t) + R(s,t-1) και δείχνουμε ότι κάθε δίχρωμος χρωματισμός του K_n περιέχει είτε κόκκινο K_s είτε μπλε K_t.
Διάλεξε μια κορυφή x. Από τις n-1 ακμές που την συνδέουν με τις υπόλοιπες κορυφές, με την αρχή του περιστερεώνα:
- είτε τουλάχιστον R(s-1,t) ακμές είναι κόκκινες,
- είτε τουλάχιστον R(s,t-1) ακμές είναι μπλε.
Πρώτη περίπτωση: Έστω V' το σύνολο των R(s-1,t) κορυφών που συνδέονται με κόκκινες ακμές προς την x. Στο επαγόμενο γράφημα πάνω στο V' υπάρχει (από τον ορισμό του R(s-1,t)) είτε:
- μπλε K_t (και τότε τελειώσαμε), είτε
- κόκκινο K_{s-1} που μαζί με την x δίνει κόκκινο K_s.
Δεύτερη περίπτωση: Ομοίως για τις μπλε ακμές.
Άμεσο άνω φράγμα με διωνυμικό συντελεστή
Από επαγωγή στη σχέση Erdős–Szekeres και την ταυτότητα των διωνυμικών συντελεστών:
R(s,t) ≤ C(s+t-2, s-1), για s,t ≥ 2
όπου C(n,k) = n!/(k!(n-k)!) ο διωνυμικός συντελεστής.
4) Γνωστές μικρές τιμές
R(3)=6, και ακόμη:
- R(3,4)=9, R(3,5)=14, R(3,6)=18, R(3,7)=23, R(3,8)=28, R(3,9)=36
- R(4)=18, R(4,5)=25
Ελάχιστες άλλες τιμές είναι γνωστές ακριβώς—ο υπολογισμός τους αυξάνει εκθετικά σε δυσκολία.
Ο μύθος του Erdős
Ο Paul Erdős έλεγε χαρακτηριστικά:
«Αν εξωγήινοι απαιτούσαν να υπολογίσουμε το R(5) για να μην καταστρέψουν τη Γη, θα μπορούσαμε ίσως να τα καταφέρουμε συγκεντρώνοντας όλους τους υπολογιστές και τους μαθηματικούς του πλανήτη. Αν όμως ζητούσαν το R(6), θα έπρεπε να προετοιμαστούμε για μάχη!»
Μέχρι σήμερα γνωρίζουμε μόνο ότι 43 ≤ R(5) ≤ 48 και 102 ≤ R(6) ≤ 165.
5) Διαγώνιοι αριθμοί Ramsey R(s)
Από το άνω φράγμα με διωνυμικούς συντελεστές:
R(s) ≤ C(2s-2, s-1) = O(4^s / √s)
Πιο συγκεκριμένα: R(s) ≲ 4^s / √(πs)
Το καλύτερο γνωστό άνω φράγμα (Thomassen, 1988): R(s) ≤ 4^s / s
Γνωστό κάτω φράγμα (πιθανοτική μέθοδος): R(s) ≥ s·2^{s/2}
Το χάσμα μεταξύ άνω και κάτω φράγματος παραμένει τεράστιο και αποτελεί ένα από τα μεγάλα ανοιχτά προβλήματα της συνδυαστικής.
6) Ιστορικό πλαίσιο
Η θεωρία Ramsey οφείλει το όνομά της στον Frank Plumpton Ramsey (1903-1930), Βρετανό μαθηματικό και φιλόσοφο που πέθανε σε ηλικία μόλις 26 ετών. Στην πρωτοποριακή του εργασία "On a Problem of Formal Logic" (1930), ο Ramsey απέδειξε ότι η πλήρης αταξία είναι αδύνατη σε επαρκώς μεγάλα συστήματα.
Οι Paul Erdős και George Szekeres (1935) ανέπτυξαν περαιτέρω τη θεωρία, εισάγοντας τους αριθμούς Ramsey στη μορφή που γνωρίζουμε σήμερα και αποδεικνύοντας τη θεμελιώδη αναδρομική σχέση που φέρει το όνομά τους.
Ασκήσεις
-
Δείξε ότι R(s,2) = R(2,s) = s για κάθε s ≥ 2.
Υπόδειξη: Τι σημαίνει «μπλε K_2» ή «κόκκινο K_2»; Ποιο είναι το μικρότερο πλήρες γράφημα που περιέχει σίγουρα s κορυφές; -
Εναλλακτική απόδειξη για R(3)=6:
Χρησιμοποίησε τη σχέση Erdős–Szekeres για να δείξεις ότι:
R(3,3) ≤ R(3,2) + R(2,3) = 3 + 3 = 6 -
Κατασκευή χρωματισμού:
Δώσε έναν ρητό δίχρωμο χρωματισμό του K_5 χωρίς μονόχρωμο τρίγωνο. Σχεδίασε το γράφημα και επαλήθευσε ότι δεν υπάρχει μονόχρωμο K_3. -
Υπολογισμός άνω φράγματος:
Χρησιμοποίησε τη σχέση Erdős–Szekeres για να δείξεις ότι R(4) ≤ 18.
Υπόδειξη: R(4) ≤ R(3,4) + R(4,3) και R(3,4) = 9. -
Γενίκευση: Εξήγησε γιατί από τη σχέση R(s,t) ≤ R(s-1,t) + R(s,t-1) προκύπτει ότι R(s,t) ≤ C(s+t-2, s-1).
Υπόδειξη: Επαγωγή και ταυτότητα Pascal: C(n,k) = C(n-1,k-1) + C(n-1,k).
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου