Alfavita Newsroom Σε κάποιο σημείο της ζωής μας όλοι έχουμε βρεθεί στην κατάσταση που κοιτάμε ένα τεστ μαθηματικών το οποίο φαντάζει αδύνατο να λυθεί. Τι θα γινόταν αν η εύρεση της λύσης ενός προβλήματος διαρκούσε σχεδόν έναν αιώνα;
Για τους μαθηματικούς που ασχολούνται με το Θεώρημα Ramsey, αυτό συμβαίνει σε μεγάλο βαθμό. Στην πραγματικότητα, μικρή πρόοδος είχε σημειωθεί στην επίλυση προβλημάτων Ramsey από τη δεκαετία του 1930.
Τώρα, οι ερευνητές του Πανεπιστημίου της Καλιφόρνιας στο Σαν Ντιέγκο, Jacques Verstraete και Sam Mattheus, βρήκαν την απάντηση στο r(4,t), ένα μακροχρόνιο πρόβλημα Ramsey που προβλημάτιζε τον κόσμο των μαθηματικών για δεκαετίες.
Ποιο ήταν το πρόβλημα Ramsey;
Στα μαθηματικά, ένα γράφημα είναι μια σειρά σημείων και οι γραμμές μεταξύ αυτών των σημείων. Το Θεώρημα Ramsey υποδηλώνει ότι αν το γράφημα είναι αρκετά μεγάλο, είναι εγγυημένο ότι θα βρείτε κάποιο είδος τάξης μέσα σε αυτό – είτε ένα σύνολο σημείων χωρίς γραμμές μεταξύ τους είτε ένα σύνολο σημείων με όλες τις πιθανές γραμμές μεταξύ τους (αυτά τα σύνολα ονομάζονται “κλίκες”). Αυτό γράφεται ως r(s,t) όπου s είναι τα σημεία με γραμμές και t είναι τα σημεία χωρίς γραμμές.
Για όσους από εμάς δεν ασχολούνται με τη θεωρία γραφημάτων, το πιο γνωστό πρόβλημα Ramsey, r(3,3), ονομάζεται μερικές φορές «το θεώρημα για τους φίλους και τους ξένους» και εξηγείται μέσω ενός πάρτι: σε μια ομάδα έξι ατόμων, θα βρείτε τουλάχιστον τρία άτομα που γνωρίζονται μεταξύ τους ή τρία άτομα που δεν γνωρίζονται μεταξύ τους. Η απάντηση στο r(3,3) είναι έξι.
«Είναι ένα γεγονός της φύσης, μια απόλυτη αλήθεια. Δεν έχει σημασία ποια είναι η κατάσταση ή ποιοι έξι άνθρωποι θα διαλέξετε – θα βρείτε τρεις ανθρώπους που όλοι γνωρίζονται μεταξύ τους ή τρεις ανθρώπους που όλοι δεν γνωρίζονται μεταξύ τους. Μπορεί να μπορέσετε να βρείτε περισσότερους, αλλά είναι εγγυημένο ότι θα υπάρχουν τουλάχιστον τρεις στη μία ή την άλλη κλίκα» ανέφερε ο Verstraete.
Τι συνέβη αφότου οι μαθηματικοί διαπίστωσαν ότι r(3,3) = 6; Φυσικά, ήθελαν να μάθουν τα r(4,4), r(5,5) και r(4,t) όπου ο αριθμός των σημείων που δεν συνδέονται είναι μεταβλητός. Η λύση για το r(4,4) είναι 18 και αποδεικνύεται χρησιμοποιώντας ένα θεώρημα που δημιουργήθηκε από τους Paul Erdös και George Szekeres τη δεκαετία του 1930.
Προς το παρόν το r(5,5) είναι ακόμη άγνωστο.
Ένα καλό πρόβλημα αντεπιτίθεται
Γιατί κάτι τόσο απλό στη διατύπωση είναι τόσο δύσκολο να λυθεί; Αποδεικνύεται ότι είναι πιο περίπλοκο από ό,τι φαίνεται. Ας υποθέσουμε ότι γνωρίζατε ότι η λύση του r(5,5) ήταν κάπου μεταξύ 40-50. Αν ξεκινούσατε με 45 σημεία, θα υπήρχαν περισσότερα από 10.234 γραφήματα για να εξετάσετε.
«Επειδή αυτοί οι αριθμοί είναι τόσο δύσκολο να βρεθούν, οι μαθηματικοί αναζητούν εκτιμήσεις. Αυτό είναι που έχουμε πετύχει ο Sam και εγώ στην πρόσφατη εργασία μας. Πώς βρίσκουμε όχι την ακριβή απάντηση, αλλά τις καλύτερες εκτιμήσεις για το ποιοι μπορεί να είναι αυτοί οι αριθμοί Ramsey;» εξηγεί ο Verstraete.
Οι φοιτητές μαθηματικών μαθαίνουν τα προβλήματα Ramsey από νωρίς, οπότε το r(4,t) ήταν στο μυαλό του Verstraete για το μεγαλύτερο μέρος της επαγγελματικής του σταδιοδρομίας. Στην πραγματικότητα, είδε για πρώτη φορά το πρόβλημα τυπωμένο στο βιβλίο «Erdös on Graphs: His Legacy of Unsolved Problems», γραμμένο από δύο καθηγητές του UC San Diego, την Fan Chung και τον αείμνηστο Ron Graham. Το πρόβλημα είναι μια υπόθεση του Erdös, ο οποίος προσέφερε 250 δολάρια στον πρώτο που θα μπορούσε να το λύσει.
Τα ψευδοτυχαία γραφήματα έδωσαν την λύση
«Πολλοί άνθρωποι έχουν σκεφτεί το r(4,t). Είναι ένα ανοιχτό πρόβλημα για πάνω από 90 χρόνια. Αλλά δεν ήταν κάτι που βρισκόταν στην πρώτη γραμμή της έρευνάς μου. Όλοι γνωρίζουν ότι είναι δύσκολο και όλοι έχουν προσπαθήσει να το λύσουν, οπότε αν δεν έχεις μια νέα ιδέα, δεν είναι πιθανό να φτάσεις πουθενά» εξήγησε ο Verstraete.
Πριν από περίπου τέσσερα χρόνια, ο Verstraete εργαζόταν πάνω σε ένα διαφορετικό πρόβλημα Ramsey με έναν μαθηματικό στο Πανεπιστήμιο του Ιλινόις-Τσικάγο, τον Dhruv Mubayi. Μαζί ανακάλυψαν ότι τα ψευδοτυχαία γραφήματα θα μπορούσαν να ενισχύσουν τις τρέχουσες γνώσεις για αυτά τα παλιά προβλήματα.
Το 1937, ο Erdös ανακάλυψε ότι η χρήση τυχαίων γραφημάτων θα μπορούσε να δώσει καλά κατώτερα όρια στα προβλήματα Ramsey. Αυτό που ανακάλυψαν οι Verstraete και Mubayi ήταν ότι η δειγματοληψία από ψευδοτυχαία γραφήματα δίνει συχνά καλύτερα όρια για τους αριθμούς Ramsey από ό,τι τα τυχαία γραφήματα. Αυτά τα όρια -ανώτερα και κατώτερα όρια στην πιθανή απάντηση- περιόριζαν το εύρος των εκτιμήσεων που μπορούσαν να κάνουν. Με άλλα λόγια, πλησίαζαν περισσότερο στην αλήθεια.
Το 2019, προς τέρψη του κόσμου των μαθηματικών, οι Verstraete και Mubayi χρησιμοποίησαν ψευδοτυχαία γραφήματα για να λύσουν το r(3,t). Ωστόσο, ο Verstraete δυσκολεύτηκε να φτιάξει ένα ψευδοτυχαίο γράφημα που θα μπορούσε να βοηθήσει στην επίλυση του r(4,t).
Άρχισε να ασχολείται με διάφορους τομείς των μαθηματικών εκτός της συνδυαστικής, όπως η πεπερασμένη γεωμετρία, η άλγεβρα και οι πιθανότητες. Τελικά ένωσε τις δυνάμεις του με τον Mattheus, έναν μεταδιδακτορικό ερευνητή της ομάδας του, του οποίου το υπόβαθρο ήταν στην πεπερασμένη γεωμετρία.
«Αποδείχθηκε ότι το ψευδοτυχαίο γράφημα που χρειαζόμασταν μπορούσε να βρεθεί στην πεπερασμένη γεωμετρία. Ο Sam ήταν το τέλειο άτομο για να έρθει και να μας βοηθήσει να φτιάξουμε αυτό που χρειαζόμασταν» δήλωσε ο Verstraete.
Μόλις είχαν το ψευδοτυχαίο γράφημα στη θέση του, έπρεπε ακόμη να λύσουν αρκετά κομμάτια των μαθηματικών. Χρειάστηκε σχεδόν ένας χρόνος, αλλά τελικά συνειδητοποίησαν ότι είχαν μια λύση: το r(4,t) είναι κοντά σε μια κυβική συνάρτηση του t. Αν θέλετε ένα πάρτι όπου θα υπάρχουν πάντα τέσσερα άτομα που όλοι γνωρίζονται μεταξύ τους ή t άτομα που δεν γνωρίζονται μεταξύ τους, θα χρειαστείτε περίπου t3 (t εις την τρίτη) άτομα παρόντα. Υπάρχει ένας μικρός αστερίσκος (στην πραγματικότητα ένα 0) επειδή πρόκειται για μια εκτίμηση και όχι για μια ακριβή απάντηση. Αλλά το t3 είναι πολύ κοντά στην ακριβή απάντηση.
Τα ευρήματα βρίσκονται υπό εξέταση στο Annals of Mathematics. Μία προέκδοση έχει ανέβει στο arXiv.
«Πραγματικά μας πήρε χρόνια για να το λύσουμε. Και υπήρχαν πολλές φορές που είχαμε κολλήσει και αναρωτιόμασταν αν θα μπορούσαμε να το λύσουμε καθόλου. Αλλά δεν πρέπει ποτέ να τα παρατάμε, όσος χρόνος και αν χρειαστεί» δήλωσε ο Verstraete, ο οποίος τόνισε τη σημασία της επιμονής, που την υπενθυμίζει συχνά στους μαθητές του. «Αν διαπιστώσετε ότι το πρόβλημα είναι δύσκολο και έχετε κολλήσει, αυτό σημαίνει ότι είναι ένα καλό πρόβλημα. Η Fan Chung είπε ότι ένα καλό πρόβλημα αντιστέκεται. Δεν μπορείτε να περιμένετε να αποκαλυφθεί μόνο του».
Ο Verstraete γνωρίζει ότι μια τέτοια επίμονη αποφασιστικότητα ανταμείβεται καλά: «Μου τηλεφώνησε η Fan Chung και μου είπε ότι μου χρωστάει 250 δολάρια».
Όλες οι σημαντικές και έκτακτες ειδήσεις σήμερα
ΕΛΜΕΠΑ: Το κορυφαίο πρόγραμμα Ειδικής Αγωγής στην Ελλάδα για διπλή μοριοδότηση
Το 1ο στην Ελλάδα Πρόγραμμα επιμόρφωσης Τεχνητής Νοημοσύνης για εκπαιδευτικούς με Πιστοποιητικό
ΑΣΕΠ: Η πιο Εύκολη Πιστοποίηση Αγγλικών για μόρια σε 2 ημέρες (δίνεις από το σπίτι σου με 95 ευρώ)
Παν.Πατρών: Μοριοδοτούμενο σεμινάριο ΕΙΔΙΚΗ ΑΓΩΓΗΣ με 65Є εγγραφή - έως 25/11
ΕΥΚΟΛΕΣ πιστοποιήσεις ΙΣΠΑΝΙΚΩΝ - ΙΤΑΛΙΚΩΝ - ΓΑΛΛΙΚΩΝ - ΓΕΡΜΑΝΙΚΩΝ για ΑΣΕΠ - Πάρτε τις ΑΜΕΣΑ
2ος Πανελλήνιος Γραπτός Διαγωνισμός ΑΣΕΠ: Τα 2 μαθήματα εξέτασης και η ύλη
