Ένα πολύ μεγάλο μικρό άλμα προς τα εμπρός στη θεωρία γραφημάτων

Στις 15 Μαρτίου, συναρπαστικές ανακοινώσεις σεμιναρίων έστειλαν θόρυβο στον τομέα της συνδυαστικής, τη μαθηματική μελέτη της μέτρησης. Τρεις συνεργάτες σχεδίαζαν να δώσουν συντονισμένες συνομιλίες την επόμενη μέρα. Τζούλιαν Σαχασραμπούντε θα απευθυνόταν σε μαθηματικούς στο Cambridge της Αγγλίας, ενώ Σάιμον Γκρίφιθς θα μοιραζόταν τα νέα στο Ρίο ντε Τζανέιρο και Μαρσέλο Κάμπος στο Σάο Πάολο. Και οι τρεις ομιλίες είχαν πανομοιότυπους τίτλους και κρυπτικές περιλήψεις δύο προτάσεων που αναφέρονταν στην «πρόσφατη πρόοδο σε ένα παλιό πρόβλημα του Erdős». Ενώ ο Paul Erdős, ένας Ούγγρος μαθηματικός που πέθανε το 1996, πόζαρε εκατοντάδες προβλήματα κατά τη διάρκεια της καριέρας του, οι κομπινατιστές μάντευαν γρήγορα το συγκεκριμένο θέμα για το οποίο σχεδίαζε να μιλήσει η τριάδα. Οι φήμες κυκλοφόρησαν για κάτι που ονομάζεται αριθμός Ramsey, μια από τις πιο δύσκολες ποσότητες για να υπολογιστεί σε όλα τα μαθηματικά.

Οι αριθμοί Ramsey έχουν δημιουργήσει μια ολόκληρη πειθαρχία που ονομάζεται θεωρία Ramsey, η οποία αναζητά αναπόδραστα μοτίβα σε μια τεράστια γκάμα συστημάτων.

Για παράδειγμα, ας υποθέσουμε ότι προσπαθείτε να κατανείμετε όλους τους ακέραιους αριθμούς σε έναν αριθμό κάδων και θέλετε να αποφύγετε την τοποθέτηση ακολουθιών ομοιόμορφων αριθμών σε οποιονδήποτε από τους κάδους. Η θεωρία Ramsey δείχνει ότι θα αποτύχεις (εκτός αν έχεις άπειρους κουβάδες). Η θεωρία μπορεί να εφαρμοστεί στα περισσότερα οτιδήποτε μπορείτε να μετρήσετε. Το κεντρικό του μάθημα είναι ότι «δεν μπορείς να δημιουργήσεις ένα εντελώς χαοτικό σύστημα», είπε ο Benny Sudakov, μαθηματικός στο Ελβετικό Ομοσπονδιακό Ινστιτούτο Τεχνολογίας της Ζυρίχης.

Ο αριθμός Ramsey ποσοτικοποιεί πόσο μεγάλο πρέπει να είναι ένα παραδειγματικό παράδειγμα προτού αναπόφευκτα προκύψουν συγκεκριμένα μοτίβα. Αλλά παρά την κεντρική του θέση, κανείς δεν μπόρεσε να υπολογίσει τον αριθμό Ramsey για όλους εκτός από το απλούστερες περιπτώσεις. Το καλύτερο που μπόρεσαν να κάνουν είναι να βρουν όρια (ή όρια) για το τι μπορεί να είναι. Ακόμη και τότε, το ανώτερο όριο που καθιέρωσε για πρώτη φορά ο Erdős και ένας συνεργάτης του πριν από σχεδόν έναν αιώνα, μόλις και μετά βίας είχε κουνηθεί.

Στη συνέχεια, στα σεμινάρια της 15ης Μαρτίου, και σε μια εργασία που δημοσιεύτηκε αργότερα εκείνο το βράδυ, οι ερευνητές ανακοίνωσαν ότι είχαν βελτιώσει το άνω όριο του αριθμού Ramsey κατά ένα εκθετικό ποσό.

«Ήμουν πατημένος», είπε Yuval Wigderson, μαθηματικός στο Πανεπιστήμιο του Τελ Αβίβ, στο άκουσμα του νέου αποτελέσματος. «Έτρεμα κυριολεκτικά για μισή ώρα έως μία ώρα».

Οι Γραμμές του Κόμματος

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

Ένα πλήρες γράφημα είναι τόσο περίπλοκο όσο και απλό — κάθε κόμβος συνδέεται με κάθε άλλο κόμβο. Ο αριθμός Ramsey περιγράφει πόσους κόμβους πρέπει να περιέχει ένα πλήρες γράφημα για να αναγκαστεί να έχει μια συγκεκριμένη δομή. Ας υποθέσουμε ότι οι άκρες ενός πλήρους γραφήματος έχουν εκχωρηθεί ένα από τα δύο χρώματα: κόκκινο ή μπλε. Και ας πούμε ότι προσπαθείτε να χρωματίσετε τις άκρες με τρόπο που να αποφεύγεται η σύνδεση μιας ομάδας κόμβων με άκρες του ίδιου χρώματος. Το 1930, ο Frank Ramsey απέδειξε ότι εάν ένα γράφημα είναι αρκετά μεγάλο, είναι αδύνατο να αποφευχθεί η δημιουργία αυτού που οι μαθηματικοί αποκαλούν μονοχρωματική κλίκα - μια ομάδα κόμβων των οποίων οι κοινές ακμές είναι είτε όλες κόκκινες είτε όλες μπλε.

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

Αλλά το μέγεθος του αριθμού Ramsey είναι δύσκολο να προσδιοριστεί. Το 1935, πέντε χρόνια αφότου ο Ramsey έδειξε ότι υπάρχει, ο Erdős και ο George Szekeres έδωσαν ένα νέο, πιο αυστηρό άνω όριο για το πόσο μεγάλος είναι ο αριθμός Ramsey για μια κλίκα ενός δεδομένου μεγέθους. Αλλά από τότε, οι μαθηματικοί μετά βίας κατάφεραν να βελτιώσουν τον υπολογισμό των Erdős και Szekeres.

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

"Το πιο απλό πράγμα που μπορείτε να έχετε σε ένα γράφημα είναι μια μονόχρωμη κλίκα", είπε Μαρία Τσούντνοφσκι, μαθηματικός στο Πανεπιστήμιο του Πρίνστον. «Είναι εκπληκτικό ότι σε κάθε τεράστιο γράφημα μπορείς να βρεις ένα μεγάλο από αυτά. Δεν είναι εντελώς ξεκάθαρο».

Οι πρώτοι αριθμοί Ramsey είναι σχετικά απλοί στον υπολογισμό. Ας υποθέσουμε ότι θέλετε να μάθετε το μέγεθος του μικρότερου γραφήματος που πρέπει αναπόφευκτα να περιέχει μια κλίκα μεγέθους δύο ή R(2) για τους μαθηματικούς. Δεδομένου ότι ένα πλήρες γράφημα με δύο κόμβους είναι μόνο δύο κόμβοι που συνδέονται με μια ακμή και αυτή η άκρη πρέπει να είναι είτε κόκκινη είτε μπλε, το R(2) είναι 2. Γενικότερα, R(k), ή τον αριθμό Ramsey του k, είναι ο ελάχιστος αριθμός κόμβων πέραν του οποίου ένα γράφημα δεν μπορεί να αποφύγει να περιέχει μια κλίκα μεγέθους k.

Δεν είναι τόσο δύσκολο να δείξουμε ότι ο αριθμός Ramsey για μια κλίκα μεγέθους 3, ή R(3), είναι 6 (δείτε το γράφημα). Αλλά μόλις το 1955 το R(4) καθηλώθηκε στο 18. Το R(5) παραμένει άγνωστο — είναι τουλάχιστον 43 και όχι μεγαλύτερος από 48. Αν και αυτοί οι αριθμοί είναι μικροί, το κοσκίνισμα όλων των πιθανών χρωματισμών είναι έξω της ερώτησης, είπε ο Ντέιβιντ Κόνλον του Ινστιτούτου Τεχνολογίας της Καλιφόρνια. Εξετάστε τον αριθμό των χρωματισμών σε ένα πλήρες γράφημα με 43 κόμβους. «Έχετε 903 άκρες. καθένα από αυτά μπορεί να χρωματιστεί με δύο τρόπους», εξήγησε. «Έτσι παίρνετε 2⁹⁰³, το οποίο είναι απλώς αστρονομικά μεγάλο».

Καθώς το μέγεθος της κλίκας αυξάνεται, το έργο του να καταγραφεί ο αριθμός Ramsey γίνεται πιο δύσκολο. Ο Erdős ειρωνεύτηκε ότι ο ολοκληρωτικός πόλεμος με μαθηματικά απαιτητικούς εξωγήινους θα ήταν ευκολότερος από την προσπάθεια υπολογίστε το R(6), που είναι κάπου μεταξύ 102 και 165. Το εύρος της αβεβαιότητας αυξάνεται γρήγορα: Σύμφωνα με εκτιμήσεις που συνέταξε ο Stanisław Radziszowski, το R(10) θα μπορούσε να είναι τόσο μικρό όσο 798 και μεγάλο όσο 23,556. Αλλά οι στόχοι των μαθηματικών ξεπερνούν πολύ τον αριθμό Ramsey των 10. Θέλουν έναν τύπο που θα δίνει μια καλή εκτίμηση του R(k), ακόμη και — ή ειδικά — όταν k είναι εξαιρετικά μεγάλο.

«Δεν γνωρίζω κάποιον σε συνδυασμό που να μην έχει σκεφτεί αυτό το πρόβλημα τουλάχιστον λίγο», είπε ο Wigderson. «Αυτό το πρόβλημα είναι, νομίζω, πολύ ιδιαίτερο».

Διάταξη στο Δικαστήριο

Ο Frank Ramsey ήταν μια εκλεκτική, λαμπρή φιγούρα που πέθανε όταν ήταν 26 ετών. Λίγες εβδομάδες πριν πεθάνει, ο Πρακτικά της Μαθηματικής Εταιρείας του Λονδίνου δημοσιεύθηκε το χαρτί στην οποία εισήγαγε τους αριθμούς Ramsey. Αυτό το έργο δεν αφορούσε καν τα γραφήματα, αλλά ένα πρόβλημα στη μαθηματική λογική. Ο Ramsey απέδειξε ότι μια δήλωση που ικανοποιεί ορισμένες προϋποθέσεις πρέπει να είναι αληθινή τουλάχιστον μερικές φορές. Μία από αυτές τις προϋποθέσεις ήταν να υπάρχει ένα μεγάλο «σύμπαν» σεναρίων για να δοκιμάσετε τη δήλωση. Ως σκαλοπάτι σε αυτό το αποτέλεσμα, ο Ramsey έδειξε ότι ο αριθμός Ramsey είναι πεπερασμένος.

Πέντε χρόνια αργότερα, οι Erdős και Szekeres έδειξαν ότι ο αριθμός Ramsey του k είναι μικρότερο από 4^k. Και 12 χρόνια μετά, Έδειξε ο Erdős ότι είναι μεγαλύτερο από περίπου $latex sqrt{2}^k$. Για να το κάνει αυτό, υπολόγισε τις πιθανότητες ένα γράφημα με τυχαία χρωματισμένες ακμές να περιέχει μια μονόχρωμη κλίκα. Αυτή η «πιθανοτική» τεχνική είχε τεράστια επιρροή στη θεωρία γραφημάτων. Επίσης παγίδευσε το R(k) ανάμεσα σε δύο εκθετικά αυξανόμενα γκολπόστ: $latex sqrt{2}^k$ και $latex 4^k$.

Καθώς οι δεκαετίες περνούσαν, πολλοί μαθηματικοί προσπάθησαν να μειώσουν το χάσμα μεταξύ των πιθανών τιμών του αριθμού Ramsey. Κάποιοι πέτυχαν: Το 1975, ο Τζόελ Σπένσερ διπλασίασε το κατώτερο όριο. Και μια σειρά από έγγραφα από Conlon, Άντριου Τόμασον και Ashwin Sah πίεσε το ανώτερο όριο κατά συντελεστή περίπου $latex 4^{log(k)^2}$ έως το 2020. Αλλά σε σύγκριση με τα μεγέθη των ορίων στον αριθμό Ramsey, αυτές οι προσαρμογές ήταν μικρές. Αντίθετα, οποιαδήποτε μείωση στο 4 στον τύπο των Erdős και Szekeres R(k) < 4^k θα ήταν μια εκθετική βελτίωση, που θα αναπτυχθεί γρήγορα καθώς k γίνεται μεγαλύτερο.

«Φαίνεται σαν μια χαριτωμένη μικρή ερώτηση», είπε Ρομπ Μόρις, μαθηματικός στο IMPA, το Ινστιτούτο Καθαρών και Εφαρμοσμένων Μαθηματικών της Βραζιλίας, στο Ρίο ντε Τζανέιρο, ο οποίος συνέγραψε το νέο αποτέλεσμα με τους Campos, Griffiths και Sahasrabudhe. «Είναι λίγο λεπτό να το εκτιμάς. Αλλά οι άνθρωποι ενδιαφέρονται πραγματικά για αυτό». Αυτό είναι πιθανώς μια υποτίμηση. «Αν το είχαν αποδείξει το 1936, ο κόσμος θα έλεγε, εντάξει, λοιπόν, ποια είναι η μεγάλη υπόθεση;» είπε ο Béla Bollobás, ο οποίος ήταν διδακτορικός σύμβουλος του Morris και του Sahasrabudhe στο Πανεπιστήμιο του Μέμφις. «Από τότε, έχει αποδειχθεί ότι είναι ένα πολύ μεγάλο πρόβλημα, γιατί με την πάροδο των ετών, έχουν γραφτεί αρκετές χιλιάδες εργασίες για διάφορες παραλλαγές του προβλήματος Ramsey». Οπως και Liana Yepremyan, ένας μαθηματικός στο Πανεπιστήμιο Emory, είπε, «Οι αριθμοί Ramsey δημιουργούν αυτή τη γέφυρα μεταξύ συνδυαστικής και πιθανότητας και γεωμετρίας».

Θεωρία παιγνίων

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

«Ήταν πραγματικά συναρπαστικό στην αρχή», θυμάται ο Sahasrabudhe. Τους πήρε μόνο περίπου ένα μήνα, είπε, για να παρουσιάσουν ένα σκίτσο της επιχειρηματολογίας τους.

Το σχέδιό τους ήταν να βασιστούν σε ιδέες που χρησιμοποιήθηκαν στην αρχική απόδειξη των Erdős και Szekeres ότι $latex R(k) < 4^k$. Για να αποδείξετε ότι ο αριθμός Ramsey είναι το πολύ $latex 4^k$, φανταστείτε να παίζετε ένα παιχνίδι σε ένα πλήρες γράφημα με κόμβους $latex 4^k$. Το παιχνίδι έχει δύο παίκτες. Πρώτον, ο αντίπαλός σας χρωματίζει κάθε άκρη είτε κόκκινο είτε μπλε, ελπίζοντας να χρωματίσει τις άκρες με τρόπο που να αποφεύγει τη δημιουργία μιας μονοχρωματικής κλίκας k κόμβους.

Μόλις ο αντίπαλός σας τελειώσει με το χρωματισμό, είναι δουλειά σας να αναζητήσετε μια μονόχρωμη κλίκα. Αν βρεις ένα, κερδίζεις.

Για να κερδίσετε αυτό το παιχνίδι, μπορείτε να ακολουθήσετε μια απλή στρατηγική. Σας βοηθά να σκεφτείτε (μεταφορικά) να ταξινομήσετε τους κόμβους σας σε δύο κουβάδες. Οι κόμβοι σε έναν κάδο θα σχηματίσουν μια μπλε κλίκα και οι κόμβοι στον άλλο θα σχηματίσουν μια κόκκινη κλίκα. Ορισμένοι κόμβοι θα διαγραφούν και δεν θα ακουστούν ποτέ ξανά. Στην αρχή, και οι δύο κάδοι είναι άδειοι και κάθε κόμβος είναι υποψήφιος να μπει σε έναν από τους δύο.

Ξεκινήστε με οποιονδήποτε κόμβο που σας αρέσει. Στη συνέχεια, κοιτάξτε τις συνδετικές άκρες. Εάν τα μισά ή περισσότερα από τα άκρα είναι κόκκινα, τότε διαγράψτε όλα τα μπλε άκρα και τους κόμβους με τους οποίους είναι συνδεδεμένοι. Στη συνέχεια, βάλτε την αρχική σας επιλογή στον «κόκκινο» κάδο. Όλες οι κόκκινες άκρες αυτού του κόμβου είναι ακόμα ζωντανές και καλά, προσκολλώνται στο υπόλοιπο γράφημα από το εσωτερικό του κάδου. Εάν περισσότερες από τις μισές άκρες είναι μπλε, διαγράφετε αναλόγως τις κόκκινες άκρες και τους κόμβους και το βάζετε στον μπλε κάδο.

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

Όταν τελειώσετε, κοιτάξτε μέσα στους κάδους. Επειδή ένας κόμβος μπήκε στον κόκκινο κάδο μόνο αφού εξαλειφθούν οι μπλε γείτονές του, όλοι οι κόμβοι στον κόκκινο κάδο συνδέονται με κόκκινες άκρες — σχηματίζουν μια κόκκινη κλίκα. Ομοίως, ο μπλε κάδος σχηματίζει μια μπλε κλίκα. Εάν το αρχικό σας γράφημα έχει τουλάχιστον κόμβους $latex 4^k$, μπορείτε να αποδείξετε ότι ένας από αυτούς τους κάδους πρέπει να περιέχει τουλάχιστον k κόμβους, που εγγυώνται μια μονόχρωμη κλίκα στο αρχικό γράφημα.

Αυτό το επιχείρημα είναι έξυπνο και κομψό, αλλά σας κάνει να δημιουργήσετε δύο κλίκες — μία μπλε και μία κόκκινη — παρόλο που χρειάζεστε πραγματικά μόνο μία. Θα ήταν πιο αποτελεσματικό να πηγαίνετε πάντα κόκκινο, εξήγησε ο Κόνλον. Σύμφωνα με αυτήν τη στρατηγική, θα επιλέγατε έναν κόμβο σε κάθε βήμα, θα σβήνετε τις μπλε άκρες του και θα τον ρίχνατε στον κόκκινο κουβά. Ο κόκκινος κουβάς θα γέμιζε γρήγορα και θα συγκεντρώσατε μια κόκκινη κλίκα k κόμβους στο μισό χρόνο.

Αλλά η στρατηγική σας πρέπει να λειτουργεί για κάθε κόκκινο-μπλε χρωματισμό και είναι δύσκολο να γνωρίζουμε αν μπορείτε πάντα να βρείτε έναν κόμβο με πολλές κόκκινες άκρες. Επομένως, ακολουθώντας την πρόταση του Conlon υπάρχει ο κίνδυνος να συναντήσετε έναν κόμβο που δεν έχει σχεδόν καθόλου κόκκινες άκρες συνδεδεμένες σε αυτόν. Αυτό θα σας ανάγκαζε να διαγράψετε ένα τεράστιο μέρος του γραφήματος ταυτόχρονα, αφήνοντάς σας να προσπαθείτε να δημιουργήσετε την κλίκα σας προτού ξεμείνετε από κόμβους. Για να πραγματοποιήσουν την πρόταση του Conlon, οι Griffiths, Morris και Sahasrabudhe έπρεπε να αποδείξουν ότι αυτός ο κίνδυνος μπορούσε να αποφευχθεί.

Μια εξέταση ανοιχτού βιβλίου

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

Ένα βιβλίο, στη θεωρία γραφημάτων, αποτελείται από δύο μέρη: Υπάρχει μια μονόχρωμη κλίκα, που ονομάζεται «σπονδυλική στήλη» και ένα δεύτερο, διακριτό σύμπλεγμα κόμβων που ονομάζεται «σελίδες». Σε ένα κόκκινο βιβλίο, όλες οι άκρες που συνδέουν τους κόμβους μέσα στη σπονδυλική στήλη είναι κόκκινες, όπως και οι άκρες που συνδέουν τη ράχη με τις σελίδες. Οι άκρες που συνδέουν τους κόμβους μέσα στις σελίδες, ωστόσο, μπορεί να είναι οποιοσδήποτε συνδυασμός χρωμάτων. Ο Κόνλον είχε σημειώσει στην εργασία του το 2018 ότι αν μπορείτε να βρείτε μια κόκκινη κλίκα μέσα στις σελίδες ενός βιβλίου, τότε θα μπορούσατε να τη συνδυάσετε με τη ράχη για να αποκτήσετε μια μεγαλύτερη κόκκινη κλίκα. Αυτό σας επιτρέπει να αναλύσετε μια αναζήτηση για μια μεγάλη κόκκινη κλίκα σε δύο ευκολότερες αναζητήσεις. Πρώτα, αναζητήστε ένα κόκκινο βιβλίο. Στη συνέχεια, αναζητήστε μια κλίκα στις σελίδες του βιβλίου.

Ο Griffiths, ο Morris και ο Sahasrabudhe θέλησαν να προσαρμόσουν τον αλγόριθμο που κερδίζει το παιχνίδι έτσι ώστε να δημιουργήσει ένα κόκκινο βιβλίο αντί για μια κόκκινη κλίκα. Αν και συμβιβάστηκαν με αυτό το σχέδιο μόλις λίγες εβδομάδες μετά το έργο τους, θα χρειαστούν χρόνια για να λειτουργήσει. Έπρεπε ακόμα να αποτρέψουν τον κίνδυνο να χάσουν όλα τα κόκκινα άκρα τους.

«Ήμασταν κολλημένοι για πολύ καιρό», είπε ο Κάμπος, ο οποίος εντάχθηκε στο έργο το 2021.

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

Σε όλη τη διάρκεια, η ομάδα είχε επικεντρωθεί στον αριθμό Ramsey R (k), γνωστός και ως «διαγώνιος» αριθμός Ramsey. Ένα γράφημα μεγέθους R(k) πρέπει να περιέχει k κόμβοι, όλοι συνδέονται με άκρες του ίδιου χρώματος, αλλά δεν έχει σημασία αν αυτό το χρώμα είναι κόκκινο ή μπλε. Από την άλλη πλευρά, ο «εκτός διαγώνιος» αριθμός Ramsey R(k, l) μετρά πόσο μεγάλο πρέπει να είναι ένα γράφημα προτού περιέχει είτε μια κόκκινη κλίκα με k κόμβους, ή μια μπλε κλίκα με l κόμβους. Αντί να συνεχίσει να παραβιάζει το πρόβλημα της διαγώνιας, η ομάδα αποφάσισε να δοκιμάσει την έκδοση εκτός διαγώνιου. Αυτό αποδείχθηκε αποκαλυπτικό.

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

Στη συνέχεια, οι τέσσερις μαθηματικοί χρησιμοποίησαν το νέο φράγμα στον εκτός διαγώνιο αριθμό Ramsey για να ανοίξουν το δρόμο για το διαγώνιο αποτέλεσμα. Στις αρχές Φεβρουαρίου, είχαν επιτέλους χαμηλώσει το όριο του αριθμού Ramsey κατά έναν εκθετικό παράγοντα, ένα επίτευγμα που οι μαθηματικοί επιδίωκαν για σχεδόν έναν αιώνα. Και το έκαναν εκσυγχρονίζοντας την ίδια επιχειρηματολογία που είχαν διατυπώσει οι Erdős και Szekeres το 1935.

Έψιλον, Έψιλον

Μετά τις συνομιλίες στις 16 Μαρτίου, οι παρευρισκόμενοι άρχισαν να επιβεβαιώνουν τις φήμες. Φωτογραφίες από την ομιλία του Sahasrabudhe κυκλοφόρησαν μέσω τηλεφωνημάτων και προσωπικών μηνυμάτων — ακόμη και σε α αόριστη αλλά υποδηλωτική ανάρτηση στο blog του μαθηματικού Gil Kalai. Οι Campos, Griffiths, Sahasrabudhe και Morris ισχυρίστηκαν ότι έδειξαν ότι $latex R(k) < 3.993^k$. Εκείνο το βράδυ, οι τέσσερις συγγραφείς δημοσίευσαν το έγγραφό τους στο διαδίκτυο, επιτρέποντας στους μαθηματικούς να δουν μόνοι τους τη νέα απόδειξη.

«Νομίζω ότι πολλοί από εμάς δεν περιμέναμε να δούμε μια τέτοια βελτίωση στη διάρκεια της ζωής μας, ουσιαστικά», είπε Matija Bucić, μαθηματικός στο Πανεπιστήμιο του Πρίνστον και στο Ινστιτούτο Προηγμένων Σπουδών. "Νομίζω ότι είναι ένα απολύτως εκπληκτικό αποτέλεσμα."

Πολλοί ειδικοί ελπίζουν ότι, με την κατάργηση του εκθετικού φραγμού, θα ακολουθήσει σύντομα περισσότερη πρόοδος. Οι συγγραφείς της νέας εργασίας σκόπιμα δεν ώθησαν τη μέθοδό τους στα όριά της, για να αποφύγουν να θολώσουν τα επιχειρήματά τους με περιττές λεπτομέρειες. «Με ενδιαφέρει πολύ πόσο μακριά μπορεί να φτάσει η μέθοδος, γιατί δεν έχω ιδέα», είπε ο Κάμπος.

«Είναι μια εντελώς έξυπνη, απολύτως υπέροχη απόδειξη και μια γνήσια ανακάλυψη. Οπότε τώρα περιμένω να ανοίξουν οι πύλες», είπε ο Bollobás. «Είμαι πεπεισμένος ότι σε τρία χρόνια, η συζήτηση θα είναι για πιθανές βελτιώσεις. Μπορούμε να βελτιώσουμε το 3.993 στο 3.9; Ίσως στο 3.4; Και τι γίνεται με 3;»

Η νέα απόδειξη έρχεται σε 56 σελίδες και θα χρειαστούν εβδομάδες για να επαληθευτεί πλήρως κάθε λεπτομέρεια από την κοινότητα της συνδυαστικής. Όμως οι συνάδελφοι είναι αισιόδοξοι. «Αυτή η ομάδα συγγραφέων, είναι πολύ σοβαροί άνθρωποι. Και είναι άνθρωποι που είναι πραγματικά, πολύ καλοί σε πολύ τεχνικά πράγματα», είπε ο Wigderson.

Όταν πρόκειται για τους συνεργάτες του, ο Γκρίφιθς συμφωνεί. «Είναι προνόμιο να δουλεύεις με λαμπρούς ανθρώπους, έτσι δεν είναι; Και νομίζω ότι είναι αυτό για το οποίο νιώθω πολύ ευγνώμων», είπε. «Αν μου το άφηναν, μπορεί να χρειαζόμουν άλλα πέντε χρόνια για να διορθώσω τις λεπτομέρειες».