Στη θεωρία γραφημάτων, ένα άκαμπτο γράφημα είναι ένα γράφημα που έχει πεπερασμένο αριθμό εμβυθίσεων στο 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], βελτιώνουμε τα υπάρχοντα άνω φράγματα, για την κλάση των ελαχιστικώς άκαμπτων γραφημάτων, στον αριθμό των εμβυθίσεων.