Μαθηματικοί έλυσαν πρόβλημα που τους ταλαιπωρούσε από τη δεκαετία του ’20: «Πόσους να καλέσω στο πάρτι μου»

Η έννοια αυτή προτάθηκε για πρώτη φορά από τον Frank Ramsey τη δεκαετία του 1920. Ωστόσο, από τότε που ο μαθηματικός Ramsey απέδειξε το θεώρημά του στα τέλη της δεκαετίας του 1920, το r(4,t) είχε μείνει άλυτο, μέχρι που ήρθαν στο προσκήνιο οι Sam Mattheus και Jacques Verstraete του Πανεπιστημίου της Καλιφόρνιας στο Σαν Ντιέγκο.

Παίρνοντας τα πράγματα από την αρχή, πρόκειται για ένα θέμα που μπορεί να παρομοιαστεί με κάτι αρκετά πιο καθημερινό: τον ιδανικό αριθμό καλεσμένων για ένα πάρτι.

Ειδικότερα, μια συχνή αναλογία για το πρόβλημα του Ramsey απαιτεί να σκεφτούμε πόσα άτομα πρέπει να καλέσουμε σε ένα πάρτι, έτσι ώστε τουλάχιστον τρία άτομα είτε να γνωρίζονται ήδη μεταξύ τους είτε τουλάχιστον τρία άτομα να είναι εντελώς άγνωστα μεταξύ τους. Εδώ, ο αριθμός Ramsey, r, είναι ο ελάχιστος αριθμός ατόμων που χρειάζεται στο πάρτι ώστε είτε s άτομα να γνωρίζονται μεταξύ τους είτε t άτομα να μην γνωρίζονται μεταξύ τους. Αυτό μπορεί να γραφτεί ως r(s,t), και γνωρίζουμε ότι η απάντηση είναι r(3,3) = 6.

“Είναι γεγονός της φύσης, μια απόλυτη αλήθεια. Δεν έχει σημασία ποια είναι η κατάσταση ή ποια έξι άτομα θα διαλέξετε – θα βρείτε τρία άτομα που γνωρίζονται μεταξύ τους ή τρία άτομα που δεν γνωρίζονται μεταξύ του. Μπορεί να μπορέσετε να βρείτε περισσότερους, αλλά είναι εγγυημένο ότι θα υπάρχουν τουλάχιστον τρεις που ανήκουν στη μία ή την άλλη ομάδα”, τόνισε ο Verstraete.

Οι αριθμοί Ramsey θεωρείται ότι αντιπροσωπεύουν τα όρια της χάους. Το θεώρημα προβλέπει ότι σε κάθε επαρκώς μεγάλο δίκτυο, ορισμένα μοτίβα είναι αναπόφευκτα. Κάπου στο χάος δηλαδή, πάντα υπάρχει τάξη. Και πρόκειται για αριθμούς εξαιρετικά δύσκολο να βρεθούν. Παραδοσιακά η επίλυση των συγκεκριμένων προβλημάτων γίνεται με τη χρήση γραφημάτων. Για παράδειγμα, αν κοιτάξετε την παρακάτω εικόνα, το s απεικονίζεται ως σημεία με μπλε γραμμές μεταξύ τους και το t ως σημεία με κόκκινες γραμμές. Αν ένα γράφημα είναι αρκετά μεγάλο θα βρείτε τάξη, αλλά το όλο θέμα γίνεται γρήγορα περίπλοκο.

Η έρευνα των εν λόγω μαθηματικών για τον αριθμό Ramsey r(4,t) – όπου το t αντιπροσωπεύει τον αριθμό των ξένων και το s, που έχει οριστεί σε τέσσερις, σημαίνει τους φίλους – έδωσε μια εκτίμηση που περιορίζει τον αριθμό των καλεσμένων που απαιτούνται στην υπόθεσή μας.  Η πρόκληση ήταν τρομερή και η λύση θεωρητικά άπιαστη.

“Πολλοί άνθρωποι έχουν σκεφτεί το r(4,t) – είναι ένα ανοιχτό πρόβλημα για πάνω από 90 χρόνια”, σημείωσε ο Verstraete.

Η διαδικασία εύρεσης της λύσης προφανώς δεν ήταν απλή, συνδυάζοντας την γεωμετρία με τη θεωρία γραφημάτων, μια απόδειξη της επιμονής και της διεπιστημονικής προσέγγισης που απαιτείται για την αντιμετώπιση ενός τόσο βαθιά ριζωμένου προβλήματος. Τα ευρήματα του διδύμου υποδηλώνουν ότι το r(4,t) είναι περίπου μια κυβική συνάρτηση του t, μια αποκάλυψη που απλοποιεί την κατανόηση του τρόπου με τον οποίο η τάξη αναπόφευκτα προκύπτει από το χάος. Για παράδειγμα, για ένα πάρτι με τέσσερα άτομα που γνωρίζονται μεταξύ τους ή t άτομα που δεν γνωρίζονται, χρειάζεστε t εις την 3η άτομα.

Ομοίως από το 1995 γνωρίζουμε ότι r(4,5) = 25. Οπότε περιορίζοντας τη λίστα των καλεσμένων σας σε 24, θα διατηρήσετε μια πιθανότητα να μην καλέσετε ούτε τέσσερις γνωστούς ούτε πέντε αγνώστους ταυτόχρονα.

Αυτή η εκτίμηση, που μαθηματικά εκφράζεται ως r(4,t) = Ω(t^3/log^4t ) όσο το t πλησιάζει στο άπειρο, ανοίγει τις πόρτες για περαιτέρω εξερεύνηση των αριθμών Ramsey και των πρακτικών εφαρμογών τους σε τομείς όπως η επιστήμη των υπολογιστών και τα δίκτυα επικοινωνίας.