2018-04-29 11:42:15
Ο βιολόγος και ερασιτέχνης μαθηματικός 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 πως στάθηκε εξαιρετικά τυχερός για το εύρημά του.
Πηγές https://www.geekd.gr/
en.wikipedia.org – Aubrey de Grey
wikivisually.com – Hadwiger–Nelson problem
phys.org – Amateur mathematician partially solves 60-year-old problem
quantamagazine.org – Decades-Old Graph Problem Yields to Amateur Mathematician
Το πρόβλημα 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 πως στάθηκε εξαιρετικά τυχερός για το εύρημά του.
Πηγές https://www.geekd.gr/
en.wikipedia.org – Aubrey de Grey
wikivisually.com – Hadwiger–Nelson problem
phys.org – Amateur mathematician partially solves 60-year-old problem
quantamagazine.org – Decades-Old Graph Problem Yields to Amateur Mathematician
ΦΩΤΟΓΡΑΦΙΕΣ
ΜΟΙΡΑΣΤΕΙΤΕ
ΔΕΙΤΕ ΑΚΟΜΑ
ΕΠΟΜΕΝΟ ΑΡΘΡΟ
Σολομός ψητός με αρωματικό λαδολέμονο
ΣΧΟΛΙΑΣΤΕ
