Σε 1850, Thomas Penyngton Kirkman, ένας μαθηματικός όταν δεν εκπλήρωνε την κύρια ευθύνη του ως εφημέριος στην Εκκλησία της Αγγλίας, περιέγραψε το «πρόβλημά του με τη μαθήτρια»: «Δεκαπέντε νεαρές κυρίες σε ένα σχολείο βγαίνουν τρεις δίπλα για επτά ημέρες διαδοχικά: απαιτείται να κανονιστεί τους καθημερινά, έτσι ώστε κανένας δεν θα περπατήσει δύο φορές δίπλα τους».
Για έναν σύγχρονο μαθηματικό, αυτού του είδους το πρόβλημα φαίνεται καλύτερα ως υπεργράφημα - ένα σύνολο κόμβων που συλλέγονται σε ομάδες των τριών ή περισσότερων. Οι 15 μαθήτριες είναι κόμβοι και κάθε ομάδα των «τριών δίπλα» μπορεί να θεωρηθεί ως ένα τρίγωνο, με τρεις γραμμές ή άκρες, που συνδέουν τρεις κόμβους.
Το πρόβλημα του Kirkman ουσιαστικά ρωτά εάν υπάρχει μια διάταξη αυτών των τριγώνων που συνδέει όλες τις μαθήτριες μεταξύ τους, αλλά με τον πρόσθετο περιορισμό ότι κανένα τρίγωνο δεν μοιράζεται μια άκρη. Η κοινή χρήση άκρων θα σήμαινε ότι δύο μαθήτριες πρέπει να περπατήσουν μαζί περισσότερες από μία φορές. Αυτός ο περιορισμός σημαίνει ότι κάθε κορίτσι περπατά με δύο νέους φίλους κάθε μέρα για μια εβδομάδα, έτσι ώστε κάθε πιθανό ζευγάρι να μαζεύεται ακριβώς μία φορά.
Αυτό το πρόβλημα και άλλα παρόμοια έχουν ξεγελάσει τους μαθηματικούς για σχεδόν δύο αιώνες από τότε που ο Kirkman έθεσε την ερώτησή του. Το 1973, ο θρυλικός μαθηματικός Paul Erdős πόζαρε ένα παρόμοιο. Ρώτησε αν είναι δυνατό να κατασκευαστεί ένας υπεργράφος με δύο φαινομενικά ασύμβατες ιδιότητες. Πρώτον, κάθε ζεύγος κόμβων πρέπει να συνδέεται με ακριβώς ένα τρίγωνο, όπως συμβαίνει με τις μαθήτριες. Αυτή η ιδιότητα κάνει το γράφημα πυκνό με τρίγωνα. Η δεύτερη απαίτηση αναγκάζει τα τρίγωνα να απλώνονται με πολύ ακριβή τρόπο. (Συγκεκριμένα, απαιτεί ότι για οποιαδήποτε μικρή ομάδα τριγώνων, υπάρχουν τουλάχιστον τρεις περισσότεροι κόμβοι από τα τρίγωνα.) "Έχετε αυτήν την ελαφρώς αντιφατική συμπεριφορά όπου έχετε ένα πυκνό συνολικό αντικείμενο που δεν έχει πυκνά μέρη", είπε. Ντέιβιντ Κόνλον, μαθηματικός στο Ινστιτούτο Τεχνολογίας της Καλιφόρνια.
Αυτόν τον Ιανουάριο, σε μια περίπλοκη απόδειξη 50 σελίδων, τέσσερις μαθηματικοί απέδειξαν ότι είναι πάντα δυνατό να κατασκευαστεί ένας τέτοιος υπεργράφος αρκεί να έχετε αρκετούς κόμβους. "Το ποσό της τεχνικής που πέρασαν, μόνο και μόνο για να το πετύχουν αυτό, ήταν καταπληκτικό", είπε Άλαν Λο, μαθηματικός στο Πανεπιστήμιο του Μπέρμιγχαμ. Ο Κόνλον συμφώνησε: «Είναι ένα πραγματικά εντυπωσιακό έργο».
Η ερευνητική ομάδα κατασκεύασε ένα σύστημα που ικανοποιούσε τις διαβολικές απαιτήσεις του Erdős ξεκινώντας με μια τυχαία διαδικασία επιλογής τριγώνων και σχεδιάζοντας τα με εξαιρετική προσοχή ώστε να ταιριάζει στις ανάγκες τους. «Ο αριθμός των δύσκολων τροποποιήσεων που μπαίνουν στην απόδειξη είναι πραγματικά συγκλονιστικός», είπε ο Κόνλον.
Η στρατηγική τους ήταν να κατασκευάσουν προσεκτικά το υπεργράφημα από μεμονωμένα τρίγωνα. Για παράδειγμα, φανταστείτε τις 15 μαθήτριές μας. Σχεδιάστε μια γραμμή ανάμεσα σε κάθε ζευγάρι.
Ο στόχος εδώ είναι να χαράξουμε τρίγωνα πάνω από αυτές τις γραμμές, έτσι ώστε τα τρίγωνα να ικανοποιούν δύο απαιτήσεις: Πρώτον, κανένα τρίγωνο δεν μοιράζεται μια άκρη. (Τα συστήματα που πληρούν αυτή την απαίτηση ονομάζονται τριπλά συστήματα Steiner.) Και δεύτερον, βεβαιωθείτε ότι κάθε μικρό υποσύνολο τριγώνων χρησιμοποιεί έναν αρκετά μεγάλο αριθμό κόμβων.
Ο τρόπος με τον οποίο οι ερευνητές το έκαναν αυτό είναι ίσως καλύτερα κατανοητός με μια αναλογία.
Πες ότι αντί να κάνεις τρίγωνα από άκρες, χτίζεις σπίτια από τουβλάκια Lego. Τα πρώτα κτίρια που φτιάχνετε είναι υπερβολικά, με δομικές ενισχύσεις και περίτεχνα διακοσμητικά. Μόλις τελειώσετε με αυτά, αφήστε τα στην άκρη. Θα χρησιμεύσουν ως «απορροφητής» — ένα είδος δομημένου αποθέματος.
Τώρα ξεκινήστε να φτιάχνετε κτίρια από τα εναπομείναντα τούβλα σας, προχωρώντας χωρίς πολύ σχεδιασμό. Όταν η προσφορά σας σε Lego μειώνεται, μπορεί να βρεθείτε με μερικά αδέσποτα τούβλα ή σπίτια που δεν είναι δομικά ακατάλληλα. Αλλά επειδή τα κτίρια απορρόφησης είναι τόσο υπερβολικά και ενισχυμένα, μπορείτε να αφαιρέσετε μερικά τούβλα εδώ και εκεί και να τα χρησιμοποιήσετε χωρίς να φλερτάρετε την καταστροφή.
Στην περίπτωση του τριπλού συστήματος Steiner, προσπαθείτε να δημιουργήσετε τρίγωνα. Ο απορροφητής σας, σε αυτήν την περίπτωση, είναι μια προσεκτικά επιλεγμένη συλλογή ακμών. Εάν δεν μπορείτε να ταξινομήσετε το υπόλοιπο σύστημα σε τρίγωνα, μπορείτε να χρησιμοποιήσετε μερικές από τις άκρες που οδηγούν στον απορροφητή. Στη συνέχεια, όταν τελειώσετε με αυτό, χωρίζετε τον ίδιο τον απορροφητή σε τρίγωνα.
Η απορρόφηση δεν λειτουργεί πάντα. Αλλά οι μαθηματικοί έχουν μπλέξει με τη διαδικασία, βρίσκοντας νέους τρόπους να ξεπερνούν τα εμπόδια. Για παράδειγμα, μια ισχυρή παραλλαγή που ονομάζεται επαναληπτική απορρόφηση χωρίζει τις ακμές σε μια ένθετη ακολουθία σετ, έτσι ώστε το καθένα να λειτουργεί ως απορροφητής για το επόμενο μεγαλύτερο.
«Την τελευταία δεκαετία έχουν σημειωθεί τεράστιες βελτιώσεις», είπε ο Conlon. «Είναι κάτι σαν μορφή τέχνης, αλλά το έχουν φέρει πραγματικά στο επίπεδο της υψηλής τέχνης σε αυτό το σημείο».
Το πρόβλημα του Erdős ήταν δύσκολο ακόμη και με την επαναληπτική απορρόφηση. «Έγινε αρκετά σαφές πολύ γρήγορα γιατί αυτό το πρόβλημα δεν είχε λυθεί», είπε Mehtaab Sawhney, ένας από τους τέσσερις ερευνητές που το έλυσαν, μαζί με Ashwin Sah, ο οποίος μαζί με τον Sawhney είναι μεταπτυχιακός φοιτητής στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης. Μάικλ Σίμκιν, μεταδιδακτορικός υπότροφος στο Κέντρο Μαθηματικών Επιστημών και Εφαρμογών στο Πανεπιστήμιο του Χάρβαρντ. και Μάθιου Κουάν, μαθηματικός στο Ινστιτούτο Επιστήμης και Τεχνολογίας της Αυστρίας. «Υπήρχαν αρκετά ενδιαφέρουσες, αρκετά δύσκολες τεχνικές εργασίες».
Για παράδειγμα, σε άλλες εφαρμογές επαναληπτικής απορρόφησης, μόλις ολοκληρώσετε την κάλυψη ενός συνόλου — είτε με τρίγωνα, για τριπλά συστήματα Steiner, είτε με άλλες δομές για άλλα προβλήματα — μπορείτε να το εξετάσετε και να το ξεχάσετε. Οι συνθήκες του Erdős, ωστόσο, εμπόδισαν τους τέσσερις μαθηματικούς να το κάνουν αυτό. Ένα προβληματικό σύμπλεγμα τριγώνων θα μπορούσε εύκολα να περιλαμβάνει κόμβους από πολλαπλά σετ απορροφητών.
«Ένα τρίγωνο που επιλέξατε πριν από 500 βήματα, πρέπει να θυμάστε με κάποιο τρόπο πώς να το σκεφτείτε», είπε ο Sawhney.
Αυτό που τελικά κατάλαβαν οι τέσσερις ήταν ότι αν επέλεγαν τα τρίγωνά τους προσεκτικά, θα μπορούσαν να παρακάμψουν την ανάγκη να παρακολουθούν κάθε μικρό πράγμα. «Αυτό που είναι καλύτερο να κάνετε είναι να σκεφτείτε οποιοδήποτε μικρό σύνολο 100 τριγώνων και να εγγυηθείτε ότι το σύνολο τριγώνων επιλέγεται με τη σωστή πιθανότητα», είπε ο Sawhney.
Οι συγγραφείς της νέας εργασίας είναι αισιόδοξοι ότι η τεχνική τους μπορεί να επεκταθεί πέρα από αυτό το ένα πρόβλημα. Εχουν έχουν ήδη εφαρμόσει τη στρατηγική τους σε ένα πρόβλημα για Λατινικά τετράγωνα, που είναι σαν μια απλοποίηση ενός παζλ sudoku.
Πέρα από αυτό, υπάρχουν πολλά ερωτήματα που μπορεί τελικά να υποκύψουν σε μεθόδους απορρόφησης, είπε ο Kwan. «Υπάρχουν τόσα πολλά προβλήματα στη συνδυαστική, ειδικά στη θεωρία σχεδιασμού, όπου οι τυχαίες διαδικασίες είναι ένα πραγματικά ισχυρό εργαλείο». Ένα τέτοιο πρόβλημα, η εικασία Ryser-Brualdi-Stein, αφορά επίσης τα λατινικά τετράγωνα και περιμένει μια λύση από τη δεκαετία του 1960.
Αν και η απορρόφηση μπορεί να χρειάζεται περαιτέρω ανάπτυξη για να μπορέσει να λύσει αυτό το πρόβλημα, έχει διανύσει πολύ δρόμο από την έναρξή της πριν από 30, είπε Μάγια Στάιν, ο αναπληρωτής διευθυντής του Κέντρου Μαθηματικής Μοντελοποίησης στο Πανεπιστήμιο της Χιλής. "Αυτό είναι κάτι που είναι πραγματικά υπέροχο να δεις, πώς εξελίσσονται αυτές οι μέθοδοι."
