🥪 Το «Σάντουιτς» των Γράφων που Περίμενε 21 Χρόνια για την Απόδειξή του

🥪 Το Μαθηματικό «Σάντουιτς» που Χρειάστηκε 21 Χρόνια

Το 2004, οι μαθηματικοί Jeong Han Kim και Van Ha Vu διατύπωσαν μια εντυπωσιακή εικασία στη θεωρία γράφων. Η ιδέα τους έμεινε γνωστή ως Sandwich Conjecture.

Το «σάντουιτς» δεν έχει βέβαια ψωμί και τυρί. Έχει τυχαίους γράφους.

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

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

🥪 Η ιδέα των Kim–Vu

Μπορούμε άραγε να κατασκευάσουμε ταυτόχρονα τρεις τυχαίους γράφους έτσι ώστε, με πολύ μεγάλη πιθανότητα,

\[ G_{\mathrm{κάτω}} \subseteq G_{\mathrm{regular}} \subseteq G_{\mathrm{πάνω}}, \]

όπου οι δύο εξωτερικοί γράφοι είναι διωνυμικοί τυχαίοι γράφοι;
Ο δύσκολος κανονικός γράφος θα βρίσκεται τότε κυριολεκτικά «στριμωγμένος» ανάμεσα στους δύο ευκολότερους γράφους.

Γιατί είναι αυτό τόσο ισχυρό;

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

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

🔓 Η λύση

Το 2025, οι Natalie Behague, Daniel Iľkovič και Richard Montgomery ολοκλήρωσαν την απόδειξη. Η βασική τους στρατηγική ήταν να κατασκευάζουν τους γράφους ακμή προς ακμή και παράλληλα, ελέγχοντας τις πιθανότητες σε κάθε στάδιο ώστε ο ένας γράφος να παραμένει μέσα στον άλλο. Για το άλλο μισό του «σάντουιτς» αντέστρεψαν ουσιαστικά τη διαδικασία: ξεκίνησαν από πλήρεις γράφους και αφαιρούσαν ακμές.

Η σημασία του αποτελέσματος ξεπερνά την επίλυση μιας εικασίας του 2004. Δημιουργεί μια γέφυρα ανάμεσα σε δύο διαφορετικά μοντέλα τυχαιότητας και επιτρέπει να μεταφερθούν αποτελέσματα από ένα μοντέλο γράφων σε ένα άλλο.

Μερικές φορές, για να καταλάβεις έναν δύσκολο μαθηματικό κόσμο,
αρκεί να καταφέρεις να τον βάλεις ανάμεσα σε δύο απλούστερους.

📖 Διαβάστε ολόκληρο το άρθρο της Quanta Magazine:

Mathematicians Build Long-Awaited Graph Sandwich

Paulina Rowińska · Quanta Magazine · 18 Σεπτεμβρίου 2026

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →