Στη θεωρία γραφημάτων (γράφων), ένα άκαμπτο γράφημα είναι ένα γράφημα που έχει πεπερασμένο αριθμό εμβυθίσεων στο $\mathbb{R}^d$, ως προς τις Ευκλείδιες κινήσεις, για δεδομένα μήκη ακμών. Η εμβύθιση γραφήματος στο $\mathbb{R}^d$ είναι μια ανάθεση των κορυφών σε σημεία στο $\mathbb{R}^d$, η οποία δημιουργεί ένα σύνολο με μήκη ακμών που αντιστοιχούν στις αποστάσεις μεταξύ των συνδεδεμένων κορυφών. Μια σημαντική κλάση άκαμπτων γραφημάτων είναι η κλάση των ελαχιστικώς άκαμπτων γραφημάτων. Ένα ελαχιστικώς άκαμπτο γράφημα, είναι ένα γράφημα που είναι άκαμπτο και έχει την ιδιότητα ότι η αφαίρεση οποιασδήποτε ακμής του, δίνει ένα γράφημα που δεν είναι άκαμπτο. Ένα σημαντικό ανοιχτό πρόβλημα είναι η εύρεση άνω φραγμάτων στον αριθμό τον εμβυθίσεων στο $\mathbb{R}^d$. Για ένα μεγάλο χρονικό διάστημα, μόνο το άνω φράγμα $ \mathcal{O}(2^{d\cdot|V|})$ ήταν γνωστό στον αριθμό των εμβυθίσεων, που προέρχεται από την άμεση εφαρμογή του θεωρήματος του B\'ezout. Στο [Bartzos et al., 2020], το φράγμα βελτιώθηκε για $d\geq5$, χρησιμοποιώντας τους permanent πίνακες. Πρόσφατα στο [Bartzos et al., 2021], το ασυμπτωτικό άνω φράγμα βελτιώθηκε για κάθε διάσταση. Στην ειδική περίπτωση του $d=2$, το ασυμπτωτικό άνω φράγμα βελτιώθηκε σε $\mathcal(3.7764^)$.
Είναι γνωστό ότι ο αριθμός των λύσεων ενός τετράγωνου αλγεβρικού συστήματος σχετίζεται με τον αριθμό των εμβυθίσεων. Συγκεκριμένα, ο αριθμός των μιγαδικών λύσεων ενός τέτοιου αλγεβρικού συστήματος επεκτείνει την έννοια των πραγματικών εμβυθίσεων στον μιγαδικό χώρο, επιτρέποντάς μας να φράξουμε τις μιγαδικές λύσεις χρησιμοποιώντας εργαλεία από τη μιγαδική αλγεβρική γεωμετρία.
Σε αυτή την διπλωματική, μετρώντας τους outdegree-περιορισμένους προσανατολισμούς ενός γραφήματος που σχετίζονται με τα αλγεβρικά φράγματα [Bartzos et al., 2020], βελτιώνουμε τα υπάρχοντα άνω φράγματα, για την κλάση των ελαχιστικώς άκαμπτων γραφημάτων, στον αριθμό των εμβυθίσεων.
(EL)
In graph theory, a rigid graph is a graph that has a finite number of embeddings in $\mathbb{R}^d$ up to rigid motions, with respect to a set of edge length constraints. An embedding of graph in $\mathbb{R}^d$ is an assignment of vertices to points in $\mathbb{R}^d$, which also induces a set of edge lengths that correspond to the distances between the connected vertices. An important class of rigid graphs is the class of minimally rigid graphs. A minimally rigid graph, is a graph that is rigid and has the property that the removal of any edge yields a graph that is not rigid. It is a major open problem to find tight upper bounds on the number of the embeddings in $\mathbb{R}^d$. For a long period, only the trivial bound of $\mathcal{O}(2^{d \cdot |V|})$ was known on the number of embeddings, that is derived from the direct application of B\'ezout's Theorem. In [Bartzos et al., 2020], the bound was improved for $d\geq5$, using matrix permanents. Recently in [Bartzos et al., 2021], the asymptotic bound was improved in all dimension. In the special case of $d=2$, the asymptotic upper bound was improved to $\mathcal(3.7764^)$.
It is known that the number of solutions of a well-constrained algebraic system is related to the number of embeddings. In particular, the number of the complex solutions of such an algebraic system extends the notion of real embeddings in the complex space, allowing us to bound the complex solutions, using tools from the complex algebraic geometry. In this thesis, by counting outdegree-constrained orientations of a graph that are related to the algebraic bounds [Bartzos et al., 2020], we improve the existing upper bounds, for the class of minimally rigid graphs, on the number of embeddings.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
