Πώς μπορεί ένα… σάντουιτς να βοηθήσει τους μαθηματικούς να κατανοήσουν καλύτερα το διαδίκτυο, τα κοινωνικά δίκτυα ή ακόμη και τα δίκτυα νευρώνων του εγκεφάλου; Η απάντηση βρίσκεται σε μια εντυπωσιακή ιδέα της θεωρίας γραφημάτων, η οποία ύστερα από περισσότερα από είκοσι χρόνια αναμονής απέκτησε επιτέλους πλήρη απόδειξη.
Στη θεωρία γραφημάτων, ένας γράφος αποτελείται από σημεία, τις λεγόμενες κορυφές, και γραμμές που τα συνδέουν, τις ακμές. Με τόσο απλό υλικό μπορούν να περιγραφούν εξαιρετικά σύνθετα δίκτυα: άνθρωποι και οι μεταξύ τους σχέσεις, υπολογιστές στο διαδίκτυο, συγκοινωνιακές συνδέσεις ή νευρώνες του εγκεφάλου.
Ένα από τα βασικά μοντέλα είναι ο τυχαίος διωνυμικός γράφος. Για κάθε ζεύγος κορυφών μπορούμε να φανταστούμε ότι ρίχνουμε ένα «νόμισμα»: ανάλογα με το αποτέλεσμα, τοποθετούμε ή όχι μια ακμή. Η ιδέα εμφανίστηκε στα τέλη της δεκαετίας του 1950 στις εργασίες του Edgar Gilbert και, σε παρόμοια μορφή, των Paul Erdős και Alfréd Rényi. Επειδή οι ακμές επιλέγονται σχετικά ανεξάρτητα, αυτοί οι γράφοι είναι ιδιαίτερα βολικοί για μαθηματική ανάλυση.
Υπάρχει όμως και μια πιο απαιτητική κατηγορία: οι τυχαίοι κανονικοί γράφοι, στους οποίους κάθε κορυφή έχει ακριβώς τον ίδιο αριθμό γειτόνων. Πρόκειται για δομές περισσότερο περιορισμένες και, σε αρκετές περιπτώσεις, καταλληλότερες για τη μοντελοποίηση πραγματικών δικτύων. Το τίμημα είναι ότι η μελέτη τους γίνεται πολύ δυσκολότερη, επειδή οι ακμές τους δεν μπορούν να επιλέγονται ανεξάρτητα.
Το 2004 οι Jeong Han Kim και Van Ha Vu διατύπωσαν μια τολμηρή εικασία. Πρότειναν ότι ένας μεγάλος τυχαίος κανονικός γράφος μπορεί, με πολύ μεγάλη πιθανότητα, να τοποθετηθεί ανάμεσα σε δύο κατάλληλους τυχαίους διωνυμικούς γράφους:
μικρότερος διωνυμικός γράφος ⊆ κανονικός γράφος ⊆ μεγαλύτερος διωνυμικός γράφος.
Αυτό είναι το περίφημο «graph sandwich», το μαθηματικό σάντουιτς. Οι δύο διωνυμικοί γράφοι παίζουν τον ρόλο των δύο φετών ψωμιού και ο δυσκολότερος κανονικός γράφος βρίσκεται ανάμεσά τους σαν γέμιση.
Γιατί όμως έχει τόσο μεγάλη σημασία;
Αν γνωρίζουμε ότι μια ιδιότητα υπάρχει στον μικρότερο γράφο και ότι αυτή η ιδιότητα διατηρείται όταν προσθέτουμε ακμές, τότε μπορούμε να συμπεράνουμε ότι υπάρχει και στον ενδιάμεσο κανονικό γράφο. Αντίστοιχα, ο μεγαλύτερος γράφος μπορεί να χρησιμοποιηθεί για ιδιότητες που διατηρούνται όταν αφαιρούμε ακμές. Έτσι αποτελέσματα που είναι σχετικά εύκολο να αποδειχθούν για διωνυμικούς γράφους μπορούν να μεταφερθούν σχεδόν αυτόματα στους πολύ δυσκολότερους κανονικούς γράφους.
Για δύο δεκαετίες οι μαθηματικοί κατάφεραν να αποδείξουν διάφορες ειδικές περιπτώσεις της εικασίας, αλλά το πλήρες «σάντουιτς» παρέμενε άπιαστο.
Το κρίσιμο βήμα έγινε από τους Richard Montgomery, Natalie Behague και Daniel Iľkovič. Η βασική τους ιδέα ήταν να μη δημιουργήσουν πρώτα τους γράφους και ύστερα να προσπαθήσουν να τους συγκρίνουν, αλλά να τους κατασκευάζουν ταυτόχρονα, ακμή προς ακμή.
Κατά την κατασκευή χρησιμοποιούνται κατάλληλα σταθμισμένες τυχαίες επιλογές. Όταν μια ακμή προστίθεται στον μικρότερο διωνυμικό γράφο, προστίθεται και στον κανονικό. Όταν δεν προστίθεται, μια δεύτερη πιθανότητα καθορίζει αν πρέπει να εμφανιστεί μόνο στον κανονικό γράφο, ώστε στο τέλος όλες οι κορυφές του να αποκτήσουν τον ίδιο βαθμό. Για το άλλο μισό του σάντουιτς, οι ερευνητές αντιστρέφουν ουσιαστικά τη διαδικασία: αρχίζουν από πλήρεις γράφους και αφαιρούν ακμές.
Η σημασία της απόδειξης ξεπερνά την επίλυση μιας εικασίας. Οι μαθηματικοί αποκτούν πλέον έναν μηχανισμό με τον οποίο μπορούν να μεταφέρουν ένα μεγάλο σύνολο γνωστών αποτελεσμάτων από τους καλά μελετημένους διωνυμικούς γράφους στους κανονικούς γράφους, χωρίς κάθε φορά να ξεκινούν την απόδειξη από το μηδέν. Ο Gil Kalai χαρακτήρισε το αποτέλεσμα ένα είδος «μεταθεωρήματος»: αντί να λύνει μόνο ένα πρόβλημα, προσφέρει ένα εργαλείο για πολλά άλλα.
Και ίσως αυτό είναι το ομορφότερο στοιχείο της ιστορίας: δύο μοντέλα τυχαιότητας που φαίνονται εκ πρώτης όψεως πολύ διαφορετικά αποδεικνύεται ότι είναι βαθιά συνδεδεμένα. Το μαθηματικό «σάντουιτς» δεν είναι λοιπόν απλώς ένα έξυπνο τέχνασμα· είναι μια νέα γέφυρα ανάμεσα σε διαφορετικούς κόσμους της τυχαιότητας και των πολύπλοκων δικτύων.
Πηγή: Paulina Rowińska, Mathematicians Build Long-Awaited Graph Sandwich, Quanta Magazine, 18 Σεπτεμβρίου 2026.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου