Ο φοιτητής του προγράμματος Χαράλαμπος Τζάμος θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Άνω φράγματα στον αριθμό των εμβυθίσεων των ελαχιστικώς άκαμπτων γραφημάτων
τη Δευτέρα 18 Οκτωβρίου 2021 και ώρα 11:00, μέσω τηλεμετάδοσης (https://meet110.webex.com/meet110/j.php?MTID=mf5b7bfc963fb5d654308ec328e62f511).
Σύνοψη Διπλωματικής:
Στη θεωρία γραφημάτων, ένα άκαμπτο γράφημα είναι ένα γράφημα που έχει πεπερασμένο αριθμό εμβυθίσεων στο R^d, ως προς τις Ευκλείδιες κινήσεις, για δεδομένα μήκη ακμών. Η εμβύθιση γραφήματος στο R^d είναι μια ανάθεση των κορυφών σε σημεία στο R^d, η οποία δημιουργεί ένα σύνολο με μήκη ακμών που αντιστοιχούν στις αποστάσεις μεταξύ των συνδεδεμένων κορυφών. Μια σημαντική κλάση άκαμπτων γραφημάτων είναι η κλάση των ελαχιστικώς άκαμπτων γραφημάτων. Ένα ελαχιστικώς άκαμπτο γράφημα, είναι ένα γράφημα που είναι άκαμπτο και έχει την ιδιότητα ότι η αφαίρεση οποιασδήποτε ακμής του, δίνει ένα γράφημα που είναι εύκαμπτο. Ένα σημαντικό ανοιχτό πρόβλημα είναι η εύρεση άνω φραγμάτων στον αριθμό τον εμβυθίσεων στο R^d. Για ένα μεγάλο χρονικό διάστημα, μόνο το άνω φράγμα O(2^(d|V|)) ήταν γνωστό στον αριθμό των εμβυθίσεων, που προέρχεται από την άμεση εφαρμογή του θεωρήματος του Bezout. Στο [Bartzos et al, 2020], το φράγμα βελτιώθηκε για d >= 5, χρησιμοποιώντας τους permanent πίνακες. Πρόσφατα στο [Bartzos et al, 2021], το ασυμπτωτικό άνω φράγμα βελτιώθηκε για κάθε διάσταση. Στην ειδική περίπτωση του d = 2, το ασυμπτωτικό άνω φράγμα βελτιώθηκε σε O(3.7764^|V|).
Είναι γνωστό ότι ο αριθμός των λύσεων ενός τετράγωνου αλγεβρικού συστήματος σχετίζεται με τον αριθμό των εμβυθίσεων. Συγκεκριμένα, ο αριθμός των μιγαδικών λύσεων ενός τέτοιου αλγεβρικού συστήματος επεκτείνει την έννοια των πραγματικών εμβυθίσεων στον μιγαδικό χώρο, επιτρέποντάς μας να φράξουμε τις μιγαδικές λύσεις χρησιμοποιώντας εργαλεία από τη μιγαδική αλγεβρική γεωμετρία.
Σε αυτή την διπλωματική, μετρώντας τους outdegree-περιορισμένους προσανατολισμούς ενός γραφήματος που σχετίζονται με τα αλγεβρικά φράγματα [Bartzos et al, 2020], βελτιώνουμε τα υπάρχοντα άνω φράγματα, για την κλάση των ελαχιστικώς άκαμπτων γραφημάτων, στον αριθμό των εμβυθίσεων.
Η Επιτροπή,
Ιωάννης Ζ. Εμίρης (Επιβλέπων),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Βασίλειος Ζησιμόπουλος,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Δημήτρης Φωτάκης,
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ