Αναμείνατε ολίγον τι
Επιστήμες

Ο βιολόγος Aubrey de Grey έλυσε μερικώς ένα μαθηματικό πρόβλημα 60 και πλέον ετών

Το πρόβλημα Hadwiger - Nelson

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

Το πρόβλημα Hadwiger – Nelson

Στη θεωρία των γράφων, το πρόβλημα Hadwiger-Nelson το οποίο πήρε το όνομά του από τους Hugo Hadwiger και Edward Nelson, αναφέρεται στον ελάχιστο αριθμό χρωμάτων που απαιτείται για να χρωματιστούν οι κορυφές ενός γραφήματος (χωρίς βρόχους), ώστε οι κορυφές που συνδέονται με την ίδια ακμή να μην έχουν το ίδιο χρώμα. Οι κορυφές απέχουν μεταξύ τους κατά μία μονάδα και οι κόμβοι του γραφήματος είναι δυνητικά άπειροι.

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

Όσο απλή είναι η διατύπωση του προβλήματος Hadwiger-Nelson, τόσο δύσκολη είναι η επίλυσή του – ειδικά αν υποθέσουμε ότι ο αριθμός των κορυφών που συνδέονται μεταξύ τους τείνει στο άπειρο.

Η ιστορία του προβλήματος και η πρώτη εκτίμηση της λύσης

Το πρόβλημα διατυπώθηκε για πρώτη φορά από τον Ε. Nelson το 1950 και δημοσιεύτηκε αρχικά από τον Gardner (1960). Ο Hadwiger (1945) είχε δημοσιεύσει νωρίτερα ένα σχετικό αποτέλεσμα, το οποίο και παρουσίασε σε μεταγενέστερο βιβλίο (Hadwiger 1961). Το πρόβλημα κέντρισε το ενδιαφέρον πολλών μαθηματικών και οι ερευνητές γρήγορα περιόρισαν τον απαιτούμενο αριθμών χρωμάτων, βρίσκοντας ότι ένα γράφημα άπειρων ακμών θα μπορούσε να χρωματιστεί με: όχι λιγότερα από τέσσερα και όχι περισσότερο από επτά χρώματα.

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

Η πρώτη φορά που μειώνεται ο αριθμός των χρωμάτων – από τον περασμένο αιώνα

Πριν λίγες μέρες, ο βιολόγος Aubrey de Grey δημοσίευσε ένα paper στην επιστημονική εφημερίδα arXiv.org με τίτλο “The Chromatic Number of the Plane Is at Least 5.”. Σε αυτό, περιγράφει πως η κατασκευή ενός γραφήματος του οποίου κάθε κόμβος ενώνεται με τους υπόλοιπους με ακμές μήκους μιας μονάδας, δεν μπορεί να χρωματιστεί με μόνο τέσσερα χρώματα.

Ο Aubrey de Grey που ασχολείται με τα μαθηματικά σε ερασιτεχνικό επίπεδο χρησιμοποίησε ένα εργαλείο (gadget) που περιλαμβάνει ένα μη κατευθυνόμενο γράφημα επτά κορυφών και 11 ακμών. Όταν το γράφημά του απέκτησε 20.425 κορυφές, συνειδητοποίησε ότι απαιτούνται περισσότερα από τέσσερα χρώματα.

Τελικά, ο Gray ελαχιστοποίησε το -πέντε χρωμάτων- γράφημά του σε 1.581 κορυφές και κάλεσε μαθηματικούς να το βελτιώσουν περαιτέρω. Κάποιοι αποδέχθηκαν την πρόκληση και επί του παρόντος το νέο ρεκόρ ανέρχεται στις 826 κορυφές. Πλέον, η λύση του προβλήματος απέκτησε νέα βάση και κέρδισε ξανά το ενδιαφέρον των μαθηματικών.

Όσο για τον Grey, δήλωσε στο Quanta πως στάθηκε εξαιρετικά τυχερός για το εύρημά του.

 

Πηγές

Μοιραστείτε το άρθρο

The following two tabs change content below.

Γιώτα Ζώτου

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

Αφήστε ένα σχόλιο

Επιλογές της ομάδας
σκίτσο του Άλμπερτ Αϊνστάιν
Πώς τα μυστικά των πρώτων αριθμών κάνουν τον κόσμο μας ασφαλέστερο
Πώς ο Ερατοσθένης υπολόγισε την περιφέρεια της Γης πάνω από 2000 χρόνια πριν;
Τι θα γινόταν αν ο αυτισμός ήταν ... υπερδύναμη;
Εκπληκτικές φωτογραφίες του Cassini λίγο πριν τη συντριβή του στον Κρόνο