Θεωρία Ράμσεϊ

Η θεωρία Ράμσεϊ, που πήρε το όνομά της από τον Βρετανό μαθηματικό και φιλόσοφο Φρανκ Π. Ράμσεϊ, είναι ένας κλάδος των μαθηματικών που επικεντρώνεται στην εμφάνιση τάξης σε μια υποδομή δεδομένης μιας δομής γνωστού μεγέθους. Τα προβλήματα στη θεωρία Ράμσεϊ συνήθως θέτουν ένα ερώτημα της όπως: "Πόσο μεγάλη πρέπει να είναι μια δομή για να διασφαλίζεται η διατήρηση μιας συγκεκριμένης ιδιότητας;". Πιο συγκεκριμένα, ο Ρον Γκράχαμ περιέγραψε τη θεωρία Ράμσεϊ ως "κλάδο της συνδυαστικής".

Σύμφωνα με τη θεωρία του Ράμσεϊ, από τον συνολικό αριθμό των αστεριών στον νυχτερινό ουρανό, μπορούμε πάντα να επιλέξουμε ένα υποσύνολο τους για να σχεδιάσουμε διάφορα αντικείμενα, όπως: ένα τρίγωνο, ένα τετράπλευρο, μια ομπρέλα ή ένα χταπόδι.

Παραδείγματα

Ένα τυπικό αποτέλεσμα της θεωρίας Ράμσεϊ ξεκινά με μια μαθηματική δομή η οποία στη συνέχεια κόβεται σε κομμάτια. Πόσο μεγάλη πρέπει να είναι η αρχική δομή ώστε τουλάχιστον ένα από τα κομμάτια να έχει μια δεδομένη ενδιαφέρουσα ιδιότητα; Αυτή η ιδέα μπορεί να οριστεί ως η κανονικότητα του τμήματος.

Παραδείγματος χάριν, ας θεωρήσουμε ένα πλήρες γράφημα τάξης n- δηλαδή υπάρχουν n κορυφές και κάθε κορυφή συνδέεται με όλες τις άλλες με κάποια άκρη. Ένα πλήρες γράφημα τάξης 3 ονομάζεται τρίγωνο. Τώρα χρωματίστε κάθε άκρη με κόκκινο ή μπλε χρώμα. Πόσο μεγάλο πρέπει να είναι το n για να υπάρχει ένα μπλε τρίγωνο ή ένα κόκκινο τρίγωνο; Αποδεικνύεται ότι η απάντηση είναι 6. Δείτε το άρθρο για το θεώρημα Ράμσεϊ για μια αυστηρή απόδειξη.

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

Αυτό είναι επίσης μια ειδική περίπτωση του θεωρήματος Ράμσεϊ, το οποίο δηλώνει ότι για κάθε δεδομένο ακέραιο αριθμό c, κάθε δεδομένο ακέραιο αριθμό n₁,...,n_c, υπάρχει ένας αριθμός, R(n₁,...,n_c), τέτοιος ώστε αν οι ακμές ενός πλήρους γραφήματος τάξης R(n₁,...,n_c) είναι χρωματισμένες με c διαφορετικά χρώματα, τότε για κάθε i μεταξύ 1 και c, πρέπει να περιέχει ένα πλήρες υπογράφημα τάξης ni του οποίου όλες οι ακμές έχουν χρώμα i. Η ειδική περίπτωση παραπάνω έχει c = 2 και n₁ = n₂ = 3.

Αποτελέσματα

Τα δύο βασικά θεωρήματα της θεωρίας του Ράμσεϊ είναι τα εξής:

• Το θεώρημα του Βαν ντερ Βέρντεν: Για κάθε δεδομένο c και n, υπάρχει ένας αριθμός V τέτοιος ώστε αν οι διαδοχικοί αριθμοί V είναι χρωματισμένοι με c διαφορετικά χρώματα, τότε πρέπει να περιέχει μια αριθμητική πρόοδο μήκους n, της οποίας όλα τα στοιχεία έχουν το ίδιο χρώμα.
• Θεώρημα των Χέιλς-Τζιούετ: Για κάθε δεδομένο n και c, υπάρχει ένας αριθμός H τέτοιος ώστε αν τα κελιά ενός κύβου n×n×n×...×n της διάστασης H χρωματιστούν με c χρώματα, πρέπει να υπάρχει μια γραμμή, στήλη κ.λπ. μήκους n της οποίας όλα τα κελιά έχουν το ίδιο χρώμα. Με άλλα λόγια, ένα παιχνίδι τρίλιζας πολλαπλών παικτών με n σειρές δεν μπορεί να καταλήξει σε ισοπαλία, ανεξάρτητα από το μέγεθος του n και τον αριθμό των παικτών, αν παίζετε σε ένα ταμπλό με επαρκείς διαστάσεις. Το θεώρημα Χέιλς-Τζιούετ συνεπάγεται το θεώρημα του Βαν ντερ Βέρντεν.

Ένα θεώρημα παρόμοιο με αυτό του Βαν ντερ Βάερντεν είναι το θεώρημα του Σουρ: για κάθε δεδομένο c, υπάρχει ένας αριθμός N τέτοιος ώστε αν οι αριθμοί 1, 2, ..., N χρωματιστούν με c διαφορετικά χρώματα, τότε πρέπει να υπάρχει ένα ζεύγος ακεραίων x, y τέτοιο ώστε x, y, και x+y να έχουν όλοι το ίδιο χρώμα. Υπάρχουν πολλές γενικεύσεις αυτού του θεωρήματος, όπως το θεώρημα Rado, το θεώρημα Rado-Folkman-Sanders, το θεώρημα Hindman και το θεώρημα Μίλικεν-Τέιλορ. Μια κλασική αναφορά για αυτά και πολλά άλλα αποτελέσματα της θεωρίας του Ράμσεϊ είναι το βιβλίο των Γκράχαμ, Ρότσιλντ, Σπένσερ και Σολυμόσι, το οποίο ανανεώθηκε και επεκτάθηκε το 2015 για την πρώτη νέα έκδοσή του μετά από 25 χρόνια.

Τα αποτελέσματα της θεωρίας του Ράμσεϊ έχουν γενικά δύο κύρια χαρακτηριστικά. Πρώτον, δεν είναι εποικοδομητικά: μπορούν να δείξουν ότι υπάρχει μια συγκεκριμένη δομή, αλλά δεν δίνουν καμία μέθοδο για την εύρεση αυτής της δομής (εκτός από την αναζήτηση). Αυτό συμβαίνει, λόγου χάρη, με την αρχή του "pigeonhole (περιστερώνα)". Δεύτερον, ενώ τα αποτελέσματα της θεωρίας Ράμσεϊ δείχνουν ότι επαρκώς μεγάλα αντικείμενα πρέπει απαραίτητα να περιέχουν μια δεδομένη δομή, η απόδειξη αυτών των αποτελεσμάτων συχνά απαιτεί αυτά τα αντικείμενα να είναι εξαιρετικά μεγάλα - δεν είναι ασυνήθιστο τα όρια να αυξάνονται εκθετικά, ή ακόμη και τόσο γρήγορα όσο η συνάρτηση Άκερμαν. Σε ορισμένες ειδικές περιπτώσεις, τα ανώτερα και κατώτερα όρια βελτιώνονται, αλλά αυτό δεν συμβαίνει γενικά. Σε πολλές περιπτώσεις, αυτά τα όρια είναι τεχνουργήματα της απόδειξης και δεν είναι γνωστό αν μπορούν να βελτιωθούν ουσιαστικά. Σε άλλες περιπτώσεις, είναι γνωστό ότι οποιοδήποτε όριο πρέπει να είναι εξαιρετικά μεγάλο, μερικές φορές ακόμη και μεγαλύτερο από οποιαδήποτε πρωταρχική αναδρομική συνάρτηση- δείτε το θεώρημα Πάρις-Χάρινγκτον για παράδειγμα. Ο αριθμός του Γκράχαμ, ένας από τους μεγαλύτερους αριθμούς που χρησιμοποιήθηκαν ποτέ σε μια σοβαρή μαθηματική απόδειξη, είναι ένα ανώτερο όριο για ένα πρόβλημα που σχετίζεται με τη θεωρία Ράμσεϊ. Ένα άλλο σημαντικό παράδειγμα είναι το πρόβλημα των Πυθαγόρειων τριπλών του Μπουλ .

Τα θεωρήματα Ράμσεϊ είναι κατά κανόνα ενός από τους δύο τύπους. Πολλά από αυτά τα θεωρήματα, τα οποία είναι εμπνευσμένα από το ίδιο το θεώρημα Ράμσεϊ, δηλώνουν ότι σε κάθε διαμέριση ενός μεγάλου δομημένου αντικειμένου, μία από τις κλάσεις περιέχει αναγκαστικά το δικό της δομημένο αντικείμενο, αλλά δεν δίνει καμία πληροφορία για το ποια κλάση είναι αυτή. Σε άλλες περιπτώσεις, ο λόγος για ένα αποτέλεσμα τύπου Ράμσεϊ είναι ότι η μεγαλύτερη κλάση διαμερίσματος περιέχει πάντα την επιθυμητή υποδομή. Τα αποτελέσματα του τελευταίου τύπου ονομάζονται αποτελέσματα πυκνότητας ή αποτελέσματα τύπου Turán, από το θεώρημα Turán. Αξιοσημείωτα παραδείγματα περιλαμβάνουν το θεώρημα του Szemerédi, το οποίο αποτελεί ενίσχυση του θεωρήματος Βαν ντερ Βέρντεν, και την έκδοση πυκνότητας του θεωρήματος Χέιλς-Γιούετ .

Δημοσιεύσεις

• Landman, B. M.; Robertson, A. (2004), Ramsey Theory on the Integers, Student Mathematical Library, 24, Providence, RI: AMS, ISBN 0-8218-3199-2 .
• Ramsey, F. P. (1930), «On a Problem of Formal Logic», Proceedings of the London Mathematical Society s2-30 (1): 264–286, doi:10.1112/plms/s2-30.1.264  (behind a paywall).
• Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463–470, doi:10.1007/978-0-8176-4842-8_3, ISBN 978-0-8176-4841-1, Zbl 0012.27010, http://www.numdam.org/item?id=CM_1935__2__463_0 .
• Boolos, G.; Burgess, J. P.; Jeffrey, R. (2007), Computability and Logic (5th έκδοση), Cambridge: Cambridge University Press, ISBN 978-0-521-87752-7, https://archive.org/details/computabilitylog0000bool .
• Matthew Katz and Jan Reimann An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics Student Mathematical Library Volume: 87; 2018; 207 pp; (ISBN 978-1-4704-4290-3)