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

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

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

Το πρόβλημα που αντιμετωπίζεται στο νέο έγγραφο φάνηκε, μέχρι τώρα, να μην αποτελεί εξαίρεση σε αυτόν τον κανόνα. Αναπόσπαστο για περισσότερα από 50 χρόνια, αφορά προϊόντα τανιστή – γραφήματα που έγιναν συνδυάζοντας δύο διαφορετικά γραφήματα (τα αποκαλούν G και H) με έναν συγκεκριμένο τρόπο. Το προϊόν tensor των G και H είναι ένα νέο, μεγαλύτερο γράφημα στο οποίο κάθε κόμβος αντιπροσωπεύει ένα ζεύγος κόμβων από τα αρχικά γραφήματα – ένα από το G και ένα από το H – και δύο κόμβοι του προϊόντος tensor συνδέονται εάν και οι δύο αντίστοιχοι κόμβοι τους G και οι αντίστοιχοι κόμβοι τους στο Η είναι συνδεδεμένοι.

Ας υποθέσουμε ότι είστε δάσκαλος μουσικής που θέλει να βρει καλό ντουέτο ζευγάρωμα για την πέμπτη συναυλία. Θα μπορούσατε να δημιουργήσετε ένα γράφημα του οποίου οι κόμβοι είναι οι μαθητές, με μια σύνδεση μεταξύ κάθε ζευγαριού που φτάνει καλά. Και θα μπορούσατε να δημιουργήσετε ένα δεύτερο γράφημα στο οποίο κάθε κόμβος είναι ένα διαφορετικό μουσικό όργανο, με μια σύνδεση μεταξύ δύο οργάνων εάν έχετε μουσική για ένα ντουέτο που τα χαρακτηρίζει. Το προϊόν tensor αυτών των δύο γραφημάτων θα έχει έναν κόμβο για κάθε πιθανή αντιστοίχιση ενός φοιτητή και ενός οργάνου (π.χ. Alicia στο τρομπόνι) και δύο κόμβοι θα συνδέονται όποτε οι δύο μαθητές συνεργάζονται καλά και τα δύο όργανα είναι σύμφωνος.

Το 1966, ο Stephen Hedetniemi, καθηγητής στο πανεπιστήμιο Clemson της Νότιας Καρολίνας, θεωρεί ότι η ελάχιστη ποσότητα χρωμάτων που απαιτείται από ένα προϊόν tensor είναι ίδια με τον αριθμό των χρωμάτων που απαιτούνται από ένα από τα δύο γραφήματα του – των δύο αριθμών είναι μικρότερο. “Είναι μια μεγάλη εικασία στη θεωρία γραφημάτων”, δήλωσε ο Gil Kalai από το Εβραϊκό Πανεπιστήμιο της Ιερουσαλήμ. “Πολλοί άνθρωποι προσπάθησαν να το σκεφτούν.”

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

“Εγώ προσωπικά σκέφτηκα ότι η εικασία θα έπρεπε να είναι αλήθεια, γιατί πολλοί έξυπνοι άνθρωποι το είχαν εξετάσει και θα έπρεπε να βρεθούν αντίθετα” αν υπήρχε, δήλωσε ο Anthony Bonato του Πανεπιστημίου Ryerson στο Τορόντο.

Αλλά τώρα ο ρωσικός μαθηματικός Yaroslav Shitov έχει βρει έναν απλό τρόπο για να κατασκευάσει τέτοια αντίθετα δείγματα: τα προϊόντα τανυστής που απαιτούν λιγότερα χρώματα από οποιαδήποτε από τις δύο συνιστώμενες γραφικές παραστάσεις τους. Η απόδειξη είναι “στοιχειώδης, αλλά έξυπνη”, δήλωσε ο Pavol Hell από το Πανεπιστήμιο Simon Fraser στο Burnaby του Καναδά.

Τα γραφήματα τανσκόρ συνδέονται στενά με ερωτήματα σχετικά με τον τρόπο με τον οποίο μπορούν να χαρτογραφηθούν διαφορετικά γραφήματα, και σε αυτό το πεδίο των μαθηματικών, η εικασία του Hedetniemi ήταν ίσως το μεγαλύτερο ανοικτό πρόβλημα, είπε η κόλαση. “Είναι μια σημαντική ανακάλυψη.”

Colorful Gatherings

Για να πάρετε μια αίσθηση για το είδος των πληροφοριών που μπορείτε να συλλέξετε από το χρωματισμό ένα γράφημα tensor, φανταστείτε ότι σκοπεύετε να προσκαλέσετε τους φίλους σας στην πατρίδα σας χώρα σε μια σειρά από Σαββατοκύριακα. Όπως ένας καλός οικοδεσπότης, θέλετε να συγκεντρώσετε ανθρώπους που θα απολαύσουν την εταιρεία του άλλου.

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

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

Το προϊόν tensor αυτών των δύο γραφημάτων θα έχει έναν κόμβο για κάθε αντιστοίχιση εργασίας-χόμπι και δύο κόμβοι συνδέονται εάν οι δύο εργασίες και τα δύο χόμπι είναι και οι δύο ασυμβίβαστες – ακριβώς η κατάσταση που θέλετε να αποφύγετε στις εκτομές σας το Σαββατοκύριακο. Τώρα, αν μπορείτε να χρωματίσετε τους κόμβους του προϊόντος tensor έτσι ώστε οι συνδεδεμένοι κόμβοι να έχουν διαφορετικά χρώματα, αυτό θα σας δώσει έναν τρόπο να δημιουργήσετε λίστες προσκεκλημένων για διαφορετικά Σαββατοκύριακα: Μπορείτε να προσκαλέσετε τα άτομα που αντιστοιχούν στους πράσινους κόμβους στο “πράσινο” Σαββατοκύριακο , τους κόκκινους κόμβους στο “κόκκινο” Σαββατοκύριακο και ούτω καθεξής, με τη διαβεβαίωση ότι οι ασυμβίβαστοι επισκέπτες θα επισκεφθούν τα διάφορα Σαββατοκύριακα. Ο αριθμός των χρωμάτων που χρησιμοποιήσατε σας δείχνει πόσες εβδομάδες για αποκλεισμό στο ημερολόγιό σας.

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

Ομοίως, οποιοδήποτε έγκυρο χρωματισμό για το γράφημα χόμπι θα μεταφερθεί στο προϊόν tensor. Ο Hedetniemi έκρινε ότι οποιοσδήποτε από τους δύο χρωματικούς χρωματισμούς χρησιμοποιεί λιγότερα χρώματα είναι, στην πραγματικότητα, ο καλύτερος δυνατός τρόπος για να χρωματίσει το γράφημα των τανυστήρων.

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

Ωστόσο, για περισσότερο από 50 χρόνια, οι μαθηματικοί δεν μπορούσαν να βρουν ένα ενιαίο προϊόν τανυστής που χρειάζονταν λιγότερα χρώματα από ένα από τα δύο συστατικά γραφήματα του. Η εικασία είναι αληθινή, ήταν σε θέση να δείξει, όποτε ένα από τα δύο συστατικά γραφήματα απαιτεί τέσσερα ή λιγότερα χρώματα. Και είναι επίσης αλήθεια στην ευρύτερη ρύθμιση των “κλασματικών” χρωμάτων, στις οποίες κάθε κόμβος μπορεί να ανατεθεί ένας συνδυασμός χρωμάτων – ίσως 2/3 κίτρινο και 1/3 πράσινο. (Όσον αφορά τα συμβαλλόμενα μέρη στο σπίτι του Σαββατοκύριακου, αυτό μπορεί να αντιστοιχεί σε τρεις διαφορετικούς δημοσιογράφους φίλους που παίζουν τένις και προσκαλούν δύο από αυτούς στο “κίτρινο” Σαββατοκύριακο και το τρίτο στο «πράσινο» Σαββατοκύριακο).

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

“Η γενική πεποίθηση ήταν ότι είναι πιθανό να είναι αλήθεια, αλλά ότι είναι πολύ σκληρό, με τον ένα ή τον άλλο τρόπο”, δήλωσε η Noga Alon του Πανεπιστημίου του Princeton.

Coloring Pages

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

Το Shitov αρχίζει εξετάζοντας το τι συμβαίνει όταν συνδυάζετε ένα γράφημα G με ένα από τα “εκθετικά” γραφήματα του για να σχηματίσετε ένα προϊόν tensor. Ένα εκθετικό γράφημα έχει έναν κόμβο για κάθε πιθανό χρωματισμό του G με κάποιο σταθερό αριθμό χρωμάτων (εδώ επιτρέπουμε κάθε πιθανό χρωματισμό, όχι μόνο χρωματισμούς στους οποίους οι συνδεδεμένοι κόμβοι είναι διαφορετικά χρώματα). Αν το γράφημα G έχει, για παράδειγμα, επτά κόμβους και η παλέτα μας έχει πέντε χρώματα, τότε το εκθετικό γράφημα έχει 57 κόμβους – εξ ου και το όνομα “εκθετικό”.

Επιστρέφοντας την προσοχή μας στους χρωματισμούς στους οποίους οι συνδεδεμένοι κόμβοι υποτίθεται ότι είναι διαφορετικά χρώματα, δεν έχουμε καμία εγγύηση ότι τα πέντε χρώματα στην παλέτα μας θα αρκούν για να χρωματίσουν το γράφημα G. ομοίως, ίσως δεν επαρκούν για να χρωματίσουν το εκθετικό γράφημα των 57 κόμβων. Αλλά οι μαθηματικοί έχουν από καιρό γνωρίσει ότι υπάρχει ένα γράφημα ότι αυτά τα πέντε χρώματα είναι επαρκή για το χρώμα: το προϊόν tensor από το G και το εκθετικό γράφημά του.

Όλα τα εκθετικά γραφήματα έχουν στην πραγματικότητα αυτή την ιδιότητα: Το προϊόν tensor που συνδυάζει το εκθετικό γράφημα με το γράφημα από το οποίο κατασκευάστηκε μπορεί να χρωματιστεί με ακριβώς τον ίδιο αριθμό χρωμάτων με την αρχική παλέτα που χρησιμοποιείται για να κάνει το εκθετικό γράφημα. Ο Shitov απέρριψε την εικασία του Hedetniemi δείχνοντας πώς να χτίσει ένα γράφημα G έτσι ώστε τόσο το G όσο και το εκθετικό γράφημά του να απαιτούν περισσότερα χρώματα από αυτά που υπάρχουν σε αυτή την παλέτα.

Ο Hedetniemi δήλωσε τον εαυτό του “απολύτως ενθουσιασμένος” για την επίλυση της εικασίας του μετά από τόσες δεκαετίες. Η απόδειξη του Σιτόφ “έχει κάποια κομψότητα, απλότητα και οριστική ποιότητα σε αυτό”, έγραψε σε ένα ηλεκτρονικό ταχυδρομείο.

Το νέο αντίτυπο είναι έξυπνο και εφευρετικό, λένε οι μαθηματικοί, και δεν απαιτεί σύνθετα μαθηματικά εργαλεία αιχμής. “Σε έναν θεωρητικό γράφημα, μπορείτε να εξηγήσετε την κατασκευή σε δύο προτάσεις”, δήλωσε ο Kalai.

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

Τα γραφήματα του Shitov είναι ογκώδη: Ενώ δεν έχει υπολογίσει με ακρίβεια πόσο μεγάλα είναι, εκτιμά ότι το γράφημα G έχει πιθανώς τουλάχιστον 4100 κόμβους και το εκθετικό γράφημα τουλάχιστον 410000 κόμβους – ένας αριθμός πολύ μεγαλύτερος από τον εκτιμώμενο αριθμό σωματιδίων στο παρατηρούμενο σύμπαν.

Και πάλι, το “γκράνγκουαν” είναι στο μάτι του θεατή. Στον Shitov, το αντίθετο δείγμα του είναι “όχι εξαιρετικά τεράστιο”, είπε. “Υπάρχουν αντίθετα δείγματα στα μαθηματικά [σε σύγκριση με] τα οποία είναι ένα πολύ μικρό πράγμα”.

Και ενώ είναι απίθανο να προσκαλέσετε 410000 επισκέπτες στη χώρα σας, το έργο του Shitov δεν αποκλείει την ύπαρξη πολύ μικρότερων αντικειμένων. Τώρα που οι μαθηματικοί γνωρίζουν ότι η υπόθεση του Hedetniemi είναι ψευδής, το φυσικό επόμενο ερώτημα είναι πόσο ψεύτικο είναι: πόσα λιγότερα χρώματα μπορεί να απαιτήσει ένα προϊόν tensor από τα γραφήματα που το αποτελούν και πόσο λίγοι κόμβοι και σύνδεσμοι μπορούν να έχουν αυτά τα αντίγραφα.

Εν τω μεταξύ, το νέο έγγραφο περιέχει ένα σημαντικό μάθημα για τους μαθηματικούς, δήλωσε ο Alon. «Μερικές φορές, ο λόγος που μια εικασία είναι πολύ δύσκολο να αποδειχθεί είναι απλά ότι είναι ψευδής».

Πατήστε εδώ για να συνεχίσετε

ΑΦΗΣΤΕ ΜΙΑ ΑΠΑΝΤΗΣΗ

Please enter your comment!
Please enter your name here