Η φοιτήτρια του προγράμματος Μάρθα Οικονόμου θα παρουσιάσει τη διπλωματική της εργασία με θέμα:
Ελάχιστος βαθμός και εμβυθίσεις πλήρων γραφημάτων
την Πέμπτη 21 Δεκεμβρίου 2023 και ώρα 17:15, μέσω τηλεμετάδοσης.
Σύνοψη Διπλωματικής:
Σε αυτή τη διπλωματική εργασία, όλα τα γραφήματα είναι πεπερασμένα και μπορεί να έχουν θηλιές και πολλαπλές ακμές. Έστωσαν uw και wv δύο ξεχωριστές γειτονικές ακμές σε ένα γράφημα G. Οι ακμές uw και wv καλούνται ανυψωμένες, όταν διαγράφονται από το G και προστίθεται μια νέα ακμή uv στη θέση τους. Λέγεται ότι ένα γράφημα G περιέχει μια εμβύθιση H, όταν ένα γράφημα ισομορφικό με το H μπορεί να σχηματιστεί από ένα υπογράφημα του G, ανυψώνοντας ζεύγη ακμών (και αφαιρώντας απομονωμένες κορυφές).
Η κλασική εικασία του Hadwiger συσχετίζει την ύπαρξη της κλίκας ως έλασσον ενός γραφήματος G με τον χρωματικό αριθμό του χ(G). Ειδικότερα, η εικασία του Hadwiger υποδηλώνει ότι κάθε γράφημα χωρίς θηλιά και Kt-έλασσον είναι (t-1)-χρωματίσιμο, αποτελώντας μια ευρεία γενίκευση του Θεώρηματος Τεσσάρων Χρωμάτων. Η εικασία αυτή παραμένει ακόμη ως ένα από τα ανοιχτά προβλήματα στη Θεωρία των Γραφημάτων. Κατά συνέπεια, οι σχέσεις μεταξύ του χρωματικού αριθμού ενός γραφήματος G και του μεγαλύτερου μεγέθους ενός πλήρους γραφήματος που περιέχεται στο G προσέλκυσαν πολύ ενδιαφέρον. Όσον αφορά τις εμβυθίσεις, η εικασία των Abu-Khzam και Langston υποδηλώνει ότι το πλήρες γράφημα Kt μπορεί να εμβυθιστεί σε οποιοδήποτε t-χρωματίσιμο γράφημα.
Μια παραλλαγή της, που αφορά τον ελάχιστο βαθμό αντί για τον χρωματικό αριθμό, είναι η εξής: Έστω d(t) ο μικρότερος ακέραιος έτσι ώστε κάθε απλό γράφημα ελαχίστου βαθμού τουλάχιστον d(t) να περιέχει μια εμβύθιση Kt, τότε d(t) = t-1. Σε αυτή τη διπλωματική εργασία, αναλύεται η απόδειξη για τις τιμές t ∈ {5, 6, 7 } (όπως αποδεικνύεται από τους DeVos, Kawarabayashi, Mohar και Okamura). Επιπλέον μελετάται η απόδειξη ότι η εικασία δεν αληθεύει όταν t ∈ {8, 9, 11} (όπως αποδεικνύεται από τις Collins και Heenean) καθώς και ένα αντιπαράδειγμα του Seymour για t = 10 που υποδεικνύει ότι d(t) ≥ t για τιμές t ≥ 10 διαψεύδοντας την εικασία. Τέλος, παρουσιάζονται δύο άνω φράγματα της συνάρτησης d(t), το πρώτο αφορά τις ισχυρές εμβυθίσεις όπου d(t) ≤ 200t και το δεύτερο σχετίζεται με τις ασθενείς εμβυθίσεις όπου δείχνεται ότι d(t) ≤ 7t+7.
Η Επιτροπή,
Αρχοντία Χ. Γιαννοπούλου (Επιβλέπουσα),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ.
Δημήτρης Ζώρος,
Εξωτερικός συνεργάτης
Σταύρος Κολλιόπουλος,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ.