domain: math info

text:
Keywords: Graph Rigidity Minimally rigid graph, Multihomogeneous Bézout Bound, Distance Geom etry, Asymptotic Bound, Mixed Volume

Rigidity theory is the branch of mathematics that studies the embeddings (or equivalently realizations) of graphs in an euclidean space or a manifold. If the number of realizations satisfying edge length constraints is finite up to rigid motions, then the embedding is called rigid, otherwise it is called flexible. These embeddings can be related to the real solutions of certain algebraic systems and their complex solutions extend the notion of rigidity to C d .

One of the major open problems in rigidity theory is to find tight upper bounds on the numbers of rigid graph realizations in an embedding space for a given number of vertices. Given a minimally rigid graph G(V, E), the upper bound of embeddings in R d used to be O 2 d•|V | , while for the cases of d = 2 and d = 3 it has been proved that there are graphs with Ω 2.3003 |V | and Ω 2.5198 |V | realizations respectively. In this thesis, we display methods that reduce the gap between the existing upper bounds and asymptotic lower bounds on the maximal number of realizations on euclidean spaces or spheres.

We propose two methods to compute a bound on the number of realizations using the multihomogeneous Bézout (mBézout) bound of wellconstrained algebraic systems. The first one relates the mBézout bound with the number of certain oudegreeconstrained graph orientations, while the second uses matrix permanent formulation. Then, we ex amine the exactness of these bounds on the number of complex embeddings. First with computations indicating that the mBézout bounds are tight for certain classes of graphs. Consequently, we exploit Bernstein's second theorem on the exactness of mixed volume, and relate it to the mBézout bound by analyzing the associated Newton Polytopes.

Using these two methods, we improve the upper bounds on the number of graph embed dings. A first improvement is achieved for realizations of graphs in d ≥ 5 and planar graphs in C 3 applying existing bounds on permanents and orientations of planar graphs. Then we introduce an elimination technique on a graphical construction that further decreases these bounds in all dimensions. This approach gives O 3.7764 |V | and O 6.8399 |V | as bounds for d = 2 and d = 3 respectively, which is the first improvement on the asymptotic upper bound for these cases.

Finally, we try to find edge lengths that can maximize the number of real embeddings in the plane, space and on the sphere for certain graphs. In order to achieve that, we use methods that sample efficiently a vast space of parameters. Our results provide a full classification according to their maximal number of real embeddings of all 7vertex graphs in R 2 and R 3 , while for the previously untreated case of S 2 we give a full characterization for all 6vertex graphs. We also establish new asymptotic lower bounds on the maximal number of realizations (or simply lower bounds) proving that in R 2 , S 2 and R 3 there exist graphs with Ω 2.3780 |V | , Ω 2.5198 |V | and Ω 2.6553 |V | embeddings respectively.

ΠΕΡΙΛΗΨΗ

Η Θεωρία Άκαμπτων Γράφων (Θ.Α.Γ.) είναι ο κλάδος των μαθηματικών που μελετά τις εμβυθίσεις γράφων (ή διαμορφώσεις) σε έναν ευκλείδιο χώρο ή μια πολλαπλότητα. Εφόσον ο αριθμός των εμβυθίσεων ως προς τις ευκλείδιες κινήσεις είναι πεπερασμένος για δεδομένα βάρη των ακμών του γράφου, που αντιστοιχούν σε αποστάσεις, τότε ο γράφος ονομάζεται άκαμπτος, αλλιώς ονομάζεται έυκαμπτος. Ο υπολογισμός του αριθμού αυτού μπορεί να γίνει συνδέοντας τις αποστάσεις μεταξύ κορυφών που βρίσκονται σε μία ακμή με αλγεβρικά συστήματα. Ως εκ τούτου ο αριθμός των πραγματικών ριζών αυτών των συστημάτων αντιστοιχεί στον αριθμό των διαμορφώσεων. Οι μιγαδικές ρίζες αυτών των συστημάτων επεκτείνουν την έννοια των άκαμπτων γράφων στους μιγαδικούς ευκλείδιους χώρους και τις αντίστοιχες πολλαπλότητες.

Ένα από τα βασικά ερωτήματα στην Θ.Α.Γ. είναι η αναζήτηση άνω φραγμάτων στον αριθμό των εμβυθίσεων για έναν δοσμένο αριθμό κορυφών που να μπορούν να πραγματωθούν. Το μέχρι τώρα γνωστό άνω φράγμα για κάθε ευκλείδιο χώρο διάστασης d για έναν άκαμπτο γράφο G(V, E) ήταν της τάξης του O 2 d•|V | , ενώ το μέγιστο των εμβυθίσεων που έχουν βρεθεί για συγκεκριμένους γράφους είναι της τάξης του Ω 2.3003 |V | στο επίπεδο και Ω 2.5198 |V | στον χώρο. Σε αυτή την διατριβή, αναπτύσσονται μέθοδοι που μειώνουν το κενό αυτό μεταξύ των άνω φραγμάτων και των (υπολογισμένων) κάτω φραγμάτων του μεγίστου αριθμού των εμβυθίσεων.

Για αυτόν τον σκοπό, προτείνουμε δύο μεθόδους για τον υπολογισμό του πολυομογενούς φράγματος Bézout (Π.Φ. Bézout) τετράγωνων αλγεβρικών συστημάτων.

Αρχικά, συνδέουμε το φράγμα αυτό με τον αριθμό διαφορετικών προσανατολισμένων γράφων που μπορεί να προκύψει με βάση περιορισμούς στο βαθμό εξερχόμενων ακμών κάθε κορυφής ενός αρχικά μη προσανατολισμένου γράφου. Επιπλέον, χρησιμοποιούμε την permanent πινάκων που σχετίζονται με το αλγεβρικό σύστημα. Στην συνέχεια μελετάμε την ακρίβεια αυτού του φράγματος σε σχέση με τον αριθμό εμβυθίσεων σε μιγαδικούς χώρους. Βρίσκουμε ότι ο υπολογισμός του όριου για μια πλειάδα γράφων υποδεικνύει ότι για συγκεκριμένες κλάσεις αυτό μπορεί να είναι ακριβές. Αυτό μας παρακινεί να χρησιμοποιήσουμε το δεύτερο θεώρημα του Bernstein, που αφορά την ακρίβεια των μεικτών όγκων, και να αναλύσουμε τις συνθήκες των πολυτόπων του Newton οι οποίες καθιστούν το φράγμα μας ακριβές.

Το επόμενο βήμα είναι η βελτίωση των ασυμπτωτικών άνω φραγμάτων. Εφαρμόζοντας άμεσα υπάρχοντα φράγματα των permanent και των προσανατολισμών επίπεδων γραφημάτων, βρίσκουμε μια πρώτη βελτίωση σε συγκεκριμένες κατηγορίες άκαμπτων γράφων, δηλαδή αυτών που εμβυθίζονται σε μεγάλες διαστάσεις (d ≥ 5), καθώς και επίπεδων γράφων που εμβυθίζονται στον χώρο. Έπειτα, αναπτύσσουμε μια μέθοδο που συνδέει τα άνω φράγματα στους προσανατολισμούς των γράφων με μια διαδικασία σταδιακής απαλοιφής κορυφών. Αυτή η μέθοδος μειώνει τα άνω φράγματα σε όλες τις κατηγορίες των γράφων που εξετάζουμε, σπάζοντας για πρώτη φορά τα τετριμμένα φράγματα για τις εμβυθίσεις στο επίπεδο και το χώρο, αποδεικνείοντας ότι είναι της τάξης του O 3.7764 |V | και O 6.8399 |V | αντίστοιχα.

Το τελευταίο πρόβλημα που μας απασχολεί είναι η εύρεση κάτω φραγμάτων του μεγίστου αριθμού των εμβυθίσεων συγκεκριμένων γράφων. Αυτό επιτυγχάνεται με την αναζήτηση των αποστάσεων που ταυτίζουν των αριθμό των πραγματικών λύσεων των αλγεβρικών συστημάτων με αυτό των μιγαδικών. Τα αποτελέσματά μας ταξινομούν πλήρως ως προς τον μέγιστο αριθμό διαμορφώσεων όλους τους άκαμπτους γράφους με 7 κορυφές που εμβυθίζονται στο επίπεδο και τον χώρο, καθώς και τους γράφους με 6 κορυφές που εμβυθίζονται στην σφαίρα S 2

ΣΥΝΟΠΤΙΚΗ ΠΑΡΟΥΣΙΑΣΗ ΤΗΣ ΔΙΔΑΚΤΟΡΙΚΗΣ ΔΙΑΤΡΙΒΗΣ

Η Θεωρία Άκαμπτων Γράφων (Θ.Α.Γ. Rigidity theory) αποτελεί έναν ιδιαίτερα ενεργό κλάδο των μαθηματικών. Παρόλο που οι απαρχές της εντοπίζονται στα τέλη του 19ου αιώνα [START_REF] Maxwell | On the calculation of the equilibrium and stiffness of frames[END_REF], υπάρχει ένα αυξανόμενο ενδιαφέρον τα τελευταία χρόνια που ωθείται από τις εφαρμογές της στην ρομποτική [START_REF] Krick | Stabilisation of infinitesimally rigid forma tions of multirobot networks[END_REF], την μοριακή βιολογία [START_REF] Gáspár | Rigidity and flexibility of biological networks[END_REF][START_REF] Billinge | Assigned and unassigned distance geometry: applications to biological molecules and nanos tructures[END_REF][START_REF] Liberti | On the number of realiza tions of certain Henneberg graphs arising in protein conformation[END_REF], την τεχνολογία του GPS [START_REF] Zhu | Universal rigidity and edge sparsification for sensor network localization[END_REF] και την αρχιτεκτονική [START_REF] Baglivo | Incidence and Symmetry in Design and Architecture. Cam bridge Urban and Architectural Studies[END_REF][START_REF] Emmerich | Structures Tendues et Autotendantes[END_REF]. Εκτός από τις εφαρμογές αυτές βέβαια η Θ.Α.Γ. έχει ερευνητικό ενδιαφέρον ως ανεξάρτητο μαθηματικό αντικείμενο που αλληλεπιδρά με την θεωρία γραφημάτων, την υπολογιστική άλγεβρα και την υπολογιστική γεωμετρία, όπως άλλωστε και με το συγγενικό πεδίο της Γεωμετρίας Αποστάσεων. Η Θ.Α.Γ. ασχολείται με τις εμβυθίσεις γράφων σε ευκλείδιους χώρους ή σε άλλες πολλαπλότητες. Στην παρούσα διατριβή καταπιανόμαστε με τις εμβυθίσεις απλών και μη κατευθυνόμενων γράφων σε ευκλείδιους χώρους (R d ) ή σφαίρες διάστασης d (S d ). Στην συνέχεια θα παραθέσουμε κάποιες βασικές έννοιες και ορισμούς της Θ.Α.Γ. χρησιμοποιώντας τους ευκλείδειους χώρους, που ισχύουν ανάλογα και για τις dδιάστατες σφαίρες. Η εμβύθιση ενός απλού μη κατευθυνόμενου γράφου G = (V, E) σε έναν ευκλείδειο χώρο R d είναι μια απεικόνιση V → R d που ορίζει μια διαμόρφωση (con formation) του γράφου. Κάθε διαμόρφωση ρ = {ρ 1 , ρ 2 , ρ 3 , ..., ρ |V | } επάγει ένα σύνολο αποστάσεων μεταξύ των κορυφών που αποτελούν άκρα ακμών λ = {λ u,v | (u, v) ∈ E} για λ u,v = ρ u -ρ v , όπου η συνάρτηση • υποδηλώνει την συνήθη ευκλείδια απόσταση, και θα τις ονομάζουμε αποστάσεις ακμών. Αυτές οι αποστάσεις καθορίζουν τα βάρη των ακμών για την συγκεκριμένη εμβύθιση. Εφόσον ο αριθμός όλων των διαμορφώσεων που ικανοποιούν τις επαγόμενες αποστάσεις ακμών είναι πεπερασμένος ως προς τις Ευκλείδειες κινήσεις (μετατοπίσεις και περιστροφές), τότε ο γράφος λέγεται άκαμπτος, ενώ σε αντίθετη περίπτωση ονομάζεται εύκαμπτος.

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

λ 2 u,v = d i=1 (x u,i -x v,i ) 2 (1)
όπου η μεταβλητή x u,i υποδηλώνει την iοστη συντεταγμένη της κορυφής u. Ως εκ τούτου, η έννοια των άκαμπτων γράφων επεκτείνεται στο μιγαδικό επίπεδο με τις μιγαδικές ρίζες αυτών των συστημάτων. Σημειώνουμε ότι εφόσον μια πολλαπλότητα καθορίζεται από αλγεβρικές εξισώσεις, όπως στην περίπτωση της S d , για να βρούμε τις εμβυθίσεις χρησιμοποιούμε τις αντίστοιχες εξισώσεις που μας δίνει η νόρμα, αλλά και τις εξισώσεις που καθορίζουν την πολλαπλότητα.

Στην περίπτωση των άκαμπτων γράφων, μια τροποποιημένη μορφή της Εξίσωσης 1 όπως στα [START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF][START_REF] Steffens | Mixed volume techniques for embeddings of Laman graphs[END_REF] κάνει εφικτή την χρήση εργαλείων από την θεωρία απαλοιφής. Η τροποποίηση αυτή συνίσταται στην εισαγωγή καινούριων μεταβλητών

s u = d i=1 x 2 u,i (2)
και η αντικατάστασή τους στην Εξίσωση 1. Ονομάζουμε τον συνδυασμό της τροποποιημένης Εξίσωσης 1 και της Εξίσωσης 2 για όλες τις κορυφές και ακμές του γράφου σφαιρικές εξισώσεις (sphere equations).

Η συγκεκριμένη αλγεβρική μοντελοποίηση δεν είναι η μοναδική που εφαρμόζεται στα πλαίσια της Θ.Α.Γ., καθώς συχνά χρησιμοποιούμε τους πίνακες CayleyMenger από την Γεωμετρία Αποστάσεων [START_REF] Blumenthal | Congruent Imbedding in Euclidean Space[END_REF]. Ο μηδενισμός και το πρόσημο των υποοριζουσών συγκεκριμένου μεγέθους ενός πίνακα CayleyMenger εκφράζει την εμβυθισιμότητα μιας συλλογής αποστάσεων σε έναν ευκλείδειο χώρο. Εφόσον κάποιες αποστάσεις είναι γνωστές και άλλες εκφράζονται με μεταβλητές, δημιουργούνται αφινικές πολλαπλότητες που προέρχονται από αυτές τις μηδενικές ορίζουσες και οι ρίζες τους εκφράζουν τις διαφορετικές διαμορφώσεις των γράφων. Εκτός της αφινικής πολλαπλότητας, η επιβεβαίωση της ύπαρξης πραγματικών διαμορφώσεων με αυτήν την μέθοδο χρειάζεται και την ικανοποίηση γεωμετρικών ανισώσεων που προκύπτουν από τους ίδιους πίνακες.

Έχει αποδειχθεί ότι ο διαχωρισμός μεταξύ εύκαμπτων και άκαμπτων γράφων έχει σχέση με την συνδυαστική δομή ενός γράφου για σχεδόν όλες τις εμβυθίσεις [START_REF] Graver | Combinatorial rigidity, volume 2 of Gradu ate studies in mathematics[END_REF]. Τους γράφους που είναι άκαμπτοι για κάθε τέτοια διαμόρφωση στον αντίστοιχο χώρο τους ονομάζουμε γενικά άκαμπτους γράφους (generically rigid graphs). Μια ειδική κλάση γενικά άκαμπτων γράφων είναι όσοι παύουν να είναι άκαμπτοι εφόσον αφαιρεθεί μία οποιαδήποτε ακμή. Αυτοί ονομάζονται ελαχιστικώς γενικά άκαμπτοι γράφοι (Ε.Α.Γ. generically minimally rigid graphs) και είναι αυτοί που απασχολούν την παρούσα διατριβή. Σημειώνουμε ότι οι Ε.Α.Γ. στο επίπεδο είναι γνωστοί ως γράφοι Laman (Laman graphs), ενώ τους Ε.Α.Γ. στον χώρο τους ονομάζουμε γράφους Geiringer (Geiringer graphs), εναρμονιζόμενοι με τους συγγραφείς του [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. Επίσης οι Ε.Α.Γ. γράφοι σε έναν ευκλείδειο χώρο R d είναι Ε.Α.Γ. και στην dδιάστατη σφαίρα S d [START_REF] Whiteley | Cones, infinity and onestory buildings[END_REF] (αυτή η ιδιότητα δεν ισχύει γενικά για όλες τις πολλαπλότητες διάστασης d).

Ένα βασικό θεώρημα στην Θ.Α.Γ. είναι η συνθήκη του Maxwell, σύμφωνα με την οποία αν ένας γράφος G = (V, E) είναι Ε.Α.Γ. στον R d τότε ο συνολικός αριθμός των πλευρών του είναι

|E| = d • |V | -d+1 2 , ενώ για κάθε υπογράφο G ′ = (V ′ , E ′ ) ⊂ G ισχύει η ανισότητα |E ′ | ≤ d•|V ′ |-d+1
2 . Η συγκεκριμένη συνθήκη είναι και επαρκής για τον χαρακτηρισμό των γράφων Laman [START_REF] Laman | On graphs and rigidity of plane skeletal structures[END_REF][START_REF] Pollaczekgeiringer | Über die Gliederung ebener Fachwerke[END_REF], κάτι που δεν συμβαίνει σε μεγαλύτερες διαστάσεις για τις οποίες έχουν βρεθεί συγκεκριμένα αντιπαραδείγματα. Η συνθήκη του Maxwell εκφράζει τους συνολικούς βαθμούς ελευθερίας του συστήματος που πρέπει να κορεστούν από τις ακμές ώστε ο γράφος να είναι άκαμπτος: στoν R d κάθε κορυφή έχει d βαθμούς ελευθερίας (άρα συνολικά μια διαμόρφωση |V | κορυφών έχει d•|V | βαθμούς ελευθερίας), από τους οποίους αφαιρούμε τους βαθμούς ελευθερίας των ευκλείδειων κινήσεων (d για τις μετατοπίσεις και d 2 για τις περιστροφές). Αλγεβρικά η συνθήκη του Maxwell υποδηλώνει ότι το αντίστοιχο σύστημα εξισώσεων είναι τετράγωνο, ενώ κανένα υποσύστημα δεν είναι ασυμβίβαστο. Άρα το αλγεβρικό σύστημα στους μιγαδικούς έχει πάντα τον ίδιο αριθμό λύσεων για κάθε γενική επιλογή του λ [START_REF] Sommese | The Numerical Solution of Systems of Polyno mials Arising in Engineering and Science[END_REF]. Προφανώς ο αριθμός των μιγαδικών διαμορφώσεων είναι ένα άνω φράγμα για τον μέγιστο αριθμό των πραγματικών διαμορφώσεων ενός γράφου, ο οποίος εξαρτάται από την επιλογή συγκεκριμένων αποστάσεων ακμών.

Ένα από τα βασικά ερωτήματα στην Θ.Α.Γ. είναι η εύρεση πραγματώσιμων άνω φραγμάτων στον αριθμό των εμβυθίσεων των Ε.Α.Γ. με δεδομένο αριθμό κορυφών. Μέχρι τώρα τα γνωστά άνω φράγματα δεν βελτίωναν ασυμπτωτικά το O 2 d•|V | , το οποίο μπορεί κανείς να το υπολογίσει με άμεση εφαρμογή του θεωρήματος του Bézout στην Εξίσωση 1. Παρόλο που έχουν γίνει προσπάθειες να χρησιμοποιηθούν περισσότερο πολύπλοκα εργαλεία για να βελτιώσουν αυτό το τετριμμένο όριο (όπως τον βαθμό των αλγεβρικών συστημάτων χρησιμοποιώντας Γεωμετρία Αποστάσεων [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF] ή εφαρμόζοντας το άνω φράγμα των μεικτών όγκων [START_REF] Steffens | Mixed volume techniques for embeddings of Laman graphs[END_REF]). Από την άλλη πλευρά, τα αντίστοιχα κάτω φράγματα στον μέγιστο αριθμό των διαμορφώσεων είναι αρκετά μικρότερα. Έχει υπολογιστεί ότι υπάρχουν γράφοι με Ω 2.3003 |V | διαμορφώσεις στον R 2 [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF] και Ω 2.5198 |V | διαμορφώσεις στον R 3 [START_REF] Emiris | Computer Algebra Methods for Studying and Computing Molecular Conformations[END_REF][START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF], ενώ στους μιγαδικούς χώρους έχουν βρεθεί γράφοι με Ω(2.5079 |V | ) στον C 2 [START_REF] Capco | The number of realizations of a Laman graph[END_REF][START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF], Ω 2.5698 |V | στην σφαίρα S 2 [START_REF] Gallet | Counting realizations of Laman graphs on the sphere[END_REF] και Ω 3.0683 |V | στον C 3 [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. Σημειώνουμε ότι εκτός από την εύρεση γενικών φραγμάτων, έχουν χρησιμοποιηθεί υπάρχοντα φράγματα στις μιγαδικές λύσεις αλγεβρικών συστημάτων για τις περιπτώσεις συγκεκριμένων γράφων Laman και Geiringer. Αυτά χρησιμοποιήθηκαν για να δωθεί ένας στόχος για την εύρεση αποστάσεων που μεγιστοποιούν τον αριθμό των εμβυθίσεων στους πραγματικούς [START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF].

Η βασική επιδίωξη της παρούσας θέσης είναι να μειωθεί το κενό μεταξύ των άνω και των κάτω φραγμάτων, χρησιμοποιώντας εργαλεία από την αλγεβρική γεωμετρία, την θεωρία γράφων και αναπτύσσοντας τους κατάλληλους αλγορίθμους. Η συνεισφορά της διατριβής αφορά τους τομείς που παρουσιάζονται στις παρακάτω παραγράφους. Τα πορίσματα και οι μέθοδοι έχουν δημοσιευθεί σε επιστημονικά περιοδικά [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF][START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF] ή έχουν εγκριθεί προς δημοσίευση [START_REF] Bartzos | New upper bounds for the number of embed dings of minimally rigid graphs[END_REF].

Ερευνούμε κατά πόσον το πολυομογενές φράγμα Bézout (Π.Φ. Bézout multihomoge neous Bézout bound) μπορεί να αντικαταστήσει το φράγμα των μεικτών όγκων ως ένα αποτελεσματικό άνω φράγμα των ριζών για τις σφαιρικές εξισώσεις. Γενικά, ισχύει η παρακάτω ανισότητα # πραγματικών λύσεων ≤ # μιγαδικών λύσεων ≤ μεικτός όγκος ≤ Π.Φ. Bézout ≤ Bézout όσον αφορά τον αριθμό των λύσεων ενός αλγεβρικού συστήματος και τα αντίστοιχα άνω φράγματα [START_REF] Sommese | The Numerical Solution of Systems of Polyno mials Arising in Engineering and Science[END_REF], με την πολυπλοκότητα υπολογισμού των παραπάνω να έχει αντίστροφη φορα. Όπως ήδη αναφέρθηκε για τα άνω φράγματα, το φράγμα Bézout (που υπολογίζεται με έναν απλό πολλαπλασιασμό) είναι ελάχιστα αντιπροσωπευτικό. Από την άλλη ο μεικτός όγκος που λαμβάνει υπόψιν την δομή των εξισώσεων μέσω των πολυτόπων του Newton έχει μεγάλο υπολογιστικό κόστος (λεπτομέρειες για τον υπολογισμό των φραγμάτων βρίσκονται στο Παράρτημα A Appendix A).

Για αυτόν τον σκοπό παρουσιάζουμε 2 μεθόδους που εφαρμόζονται στην περίπτωση των Ε.Α.Γ. για τον υπολογισμό του Π.Φ. Bézout το οποίο επίσης λαμβάνει υπόψιν την δομή των εξισώσεων, αλλά με μικρότερη λεπτομέρεια σε σχέση με τον μεικτό όγκο. Η πρώτη μέθοδος είναι συνδυαστική και βασίζεται στην συσχέτιση του Π.Φ. Bézout με τον αριθμό των διαφορετικών προσανατολισμών του αρχικού γράφου, με βάση περιορισμούς στον βαθμό των εξερχόμενων ακμών. Επιπλέον, έχουμε αναπτύξει έναν αναδρομικό αλγόριθμο για τον υπολογισμό όλων των πιθανών προσανατολισμών και τον υλοποιήσαμε σε γλώσσα Python. Η δεύτερη μέθοδος συσχετίζει έναν τετράγωνο πίνακα με το αλγεβρικό σύστημα με μέγεθός ∼ |E|, του οποίου η permanent δίνει το επιθυμητό άνω φράγμα.

Παρουσιάζουμε την σύγκριση μεταξύ των 2 μεθόδων ως προς τον απαιτούμενο υπολογιστικό χρόνο σε μια πλειάδα περιπτώσεων. Για τον υπολογισμό της permanent χρησιμοποιούμε τις αντίστοιχες υλοποιήσεις της maple και της Python. Η υλοποίηση του αναδρομικού αλγορίθμου είναι σημαντικά πιο γρήγορη, γεγονός που ήταν αναμενόμενο, καθώς ο αλγόριθμος του Ryser που θεωρείται ο πιο αποτελεσματικός για τον υπολογισμό της permanent ενός τετράγωνου πίνακα μεγέθους |E| έχει πολυπλοκότητα |E| 2 • 2 |E| , ενώ όλοι οι πιθανοί προσανατολισμοί ενός γράφου είναι το πολύ 2 |E| . Τα πειραματικά μας δεδομένα δείχνουν ότι στην συντριπτική πλειονότητα των περιπτώσεων γράφων Laman και σε όλες των γράφων Geiringer με |V | ≤ 11 ο μεικτός όγκος και το Π.Φ. Bézout των σφαιρικών εξισώσεων ταυτίζονται. Επιπλέον, όλοι οι γράφοι Geiringer με |V | ≤ 10 που είναι επίπεδοι γραφοθεωρητικά έχουν ίσο Π.Φ. Bézout και αριθμό μιγαδικών διαμορφώσεων. Για τους επίπεδους γράφους Laman αυτή η ισότητα σπάνια ισχύει στις ενδιαφέρουσες περιπτώσεις των εμβυθίσεων στο επίπεδο, αλλά ισχύει για τις εμβυθίσεις τους στην σφαίρα S 2 . Και στις 2 προαναφερθείσες κλάσεις το Π.Φ. Bézout για τους μη επίπεδους γράφους είναι αυστηρό άνω φράγμα.

Τα παραπάνω αποτελέσματα λειτουργούν ως κίνητρο για την μελέτη των συνθηκών που δείχνουν ότι το Π.Φ. Bézout είναι ακριβές. Για αυτόν τον σκοπό εφαρμόζουμε το 2ο θεώρημα του Bernstein, που αφορά την ακρίβεια του μεικτού όγκου [START_REF] Bernstein | The number of roots of a system of equations[END_REF]. Προσαρμόζουμε τα πολύτοπα του Newton στην περίπτωση των αλγεβρικών συστημάτων που έχουν πλήρη πολυομογενή δομή. Συνεπακόλουθα, αναπτύσσουμε μια μέθοδο και έναν αλγόριθμο που πιστοποιεί τα κριτήρια που θέτει το θεώρημα του Bernstein διενεργώντας πολύ λιγότερους ελέγχους από όσους προβλέπονται.

Οι μέθοδοι υπολογισμού του Π.Φ. Bézout χρησιμοποιούνται για την εξαγωγή γενικών άνω φραγμάτων στα πλαίσια της παρούσας διατριβής. Αρχικά εφαρμόζουμε το φράγμα BrègmanMinc για τις permanent πινάκων, βελτιώνοντας για πρώτη φορά τα ασυμπτωτικά φράγματα Ε.Α.Γ. σε διάσταση d ≥ 5 σε σχέση με το τετριμμένο Bézout φράγμα. Επιπλέον, αποδεικνύουμε ότι η άμεση χρήση φραγμάτων για τον προσανατολισμό επίπεδων γράφων [START_REF] Felsner | On the number of planar orientations with prescribed degrees[END_REF] μειώνει το ασυμπτωτικό άνω φράγμα για τους επίπεδους Geiringer γράφους.

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

Αυτή η μέθοδος αφορά γραφικές στις οποίες μελετήσαμε προσανατολισμούς με σταθερό αριθμό εισερχόμενων ακμών για κάθε κορυφή. Δείχνουμε ότι ο αριθμός αυτών των προσανατολισμών ταυτίζεται με αυτούς που χρησιμοποιούμε για τον υπολογισμό του Π.Φ. Bézout των σφαιρικών εξισώσεων και εφαρμόζουμε μια τεχνική απαλοιφής που οδηγεί σε ένα άνω φράγμα για αυτούς. Το άνω φράγμα στον αριθμό των προσανατολισμών δίνει βελτιωμένα άνω φράγματα για όλες τις διαστάσεις σε σχέση και με το Bézout φράγμα, αλλά και με το Brègman Σε σχέση με τα κάτω όρια στον μέγιστο αριθμό πραγματικών διαμορφώσεων, ασχολούμαστε με τις περιπτώσεις των εμβυθίσεων στο επίπεδο, το χώρο και την σφαίρα. Για να το πετύχουμε αυτό εφαρμόζουμε μεθόδους αναζήτησης των κατάλληλων αποστάσεων πλευράς που μεγιστοποιούν αυτόν τον αριθμό. Σε κάθε γράφο ο στόχος ήταν ο αριθμός των μιγαδικών διαμορφώσεων, καθώς εικάζεται ότι για την πλειονότητα των Ε.Α.Γ. συμπίπτει με τον αριθμό πραγματικών διαμορφώσεων (αλλά όχι για όλες [START_REF] Jackson | Equivalent realisations of a rigid graph[END_REF]). Για αυτόν τον λόγο χρησιμοποιούμε τόσο τις εξισώσεις σφαίρας, όσο και τις εξισώσεις κα τις ανισώσεις που δίνουν οι ορίζουσες των πίνακων CayleyMenger από την γεωμετρία αποστάσεων. Εφαρμόζουμε κλασσικές μεθόδους αναζήτησης παραμέτρων για την αύξηση των πραγματικών ριζών ενός αλγεβρικού συστήματος (αναζήτηση κοντά σε παραμέτρους που απειρίζουν τον αριθμό των λύσεων, στοχαστικές μέθοδοι, μέθοδος κυλινδρικής αλγεβρικής ανάλυσης CAD). Επιπλέον χρησιμοποιούμε τον αλγόριθμο του J.Legerský (ενός από τους συγγραφείς του [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF] του οποίου αποτελέσματα παρουσιάζονται στην παρούσα διατριβή) που αυξάνει τον αριθμό των διαμορφώσεων στον R 3 βασισμένος στην μέθοδο των καμπυλών σύνδεσης (coupler curves) που είχε ξαναχρησιμοποιηθεί στην Θ.Α.Γ. [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF]. [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF].

Κεφάλαιο 4 Άνω φράγματα για τον αριθμό των διαμορφώσεων των Ε.Α.Γ. (Up per bounds on the embedding number of minimally rigid graphs). Αυτό το κεφάλαιο χωρίζεται σε δυο μέρη. Στο πρώτο, παρουσιάζονται εφαρμογές υπαρχόντων άνω φραγμάτων στις μεθόδους που παρουσιάστηκαν στο προηγούμενο Κεφάλαιο και αποτελούν μέρος του [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF]. Στο δεύτερο, αναπτύσσουμε μια καινούρια μέθοδο που φράσσει τον αριθμό των πιθανών προσανατολισμών ενός γράφου και τελικά οδηγεί σε βελτιωμένα άνω φράγματα για όλες τις διαστάσεις εμβύθισης. Η μέθοδος αυτή και τα αποτελέσματά της έχουν εγκριθεί προς δημοσίευση [START_REF] Bartzos | New upper bounds for the number of embed dings of minimally rigid graphs[END_REF].

Κεφάλαιο 5 Ο μέγιστος αριθμός εμβυθίσεων γράφων στο επίπεδο, τον χώρο και την σφαίρα (On the maximal number of real embeddings in R 2 , R 3 and S 2 ). Σε αυτό το κεφάλαιο παρουσιάζονται τα αποτελέσματα και οι μέθοδοι που οδήγησαν στην αύξηση των κάτω φραγμάτων για τον μέγιστο αριθμό εμβυθίσεων. Τα αποτελέσματά αυτού του Κεφαλαίου ως προς τον R 3 έχουν δημοσιευθεί στα πρακτικά του International Symposium on Symbolic and Algebraic Computation 2018 (ISSAC'18) [START_REF] Bartzos | On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs[END_REF]. Η επέκταση αυτών των αποτελεσμάτων με τα αντίστοιχα στο επίπεδο και την σφαίρα αποτελούν αντικείμενο του [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF].

Κεφάλαιο 6 Συμπεράσματα και ανοιχτά ερωτήματα (Conclusion and open ques tions).

Στο τελευταίο κεφάλαιο αναλύονται τα βασικά συμπεράσματα της παρούσας διατριβής, καθώς και τα ερευνητικά ερωτήματα που προκύπτον και μπορούν να διερευνηθούν στο μέλλον. program, the ARCADES Network. I also thank him for the continuous guidance he offered to me all these years and his eagerness to transmit me his knowledge on various topics. I must say that I was always overwhelmed by his deep intuition in all our research problems. Finally, I want to thank him for his support in every issue that was not directly related to my PhD.

I would also like to thank all my colleagues in ΕρΓΑ Lab that were always willing to share their ideas and contributed to a great work atmosphere: Christos Conaxis who offered al ways a great aid for every administration issues and he also helped me to learn the basics on Computer Algebra, Clément Laroche (also an ARCADES member) who was always happy to talk about research and other issues in different occasions, Yannis Psarros who helped me understand some basics on the embedding problem which is the core of my thesis, Charalambos Tzamos who actually works with me in a new project on rigidity the ory, and also Anna Karasoulou, Vangelis Anagnostopoulos, Manolis Christoforou, Tolis Halkis, Christina Katsamaki and Apostolos Florakis. Special thanks to Michalis Samaris, who made me aware of ARCADES PhD program (though not an ΕρΓΑ lab member) and was always willing to give me his view on graph theoretical issues of my research.

I would like to thank all the other PhD fellows in the ARCADES network for the time we spent together and the ideas we exchanged: Sotiris Chouliaras, Konstantinos Gavriil, Fa nis Katsoulis, Alvaro Fuentes Suarez, Yairon Cid Ruiz, Fatmanur Yıldırım, Ahmed Blidia, Francesco Patrizi, Andrea Raffo, Michael Jimenez and especially Jan Legerský who was a great help during my stay in Austria and an excellent collaborator on the research project we worked together.

I also like to thank the other coauthors of my papers, Elias Tsigaridas, Joseph Schicho and Raimundas Vidunas for the common time we spent together working on various projects. Especially, I would also like to thank Joseph Schicho for his hospitality during my sec ondment in Linz University. In the same period, I enjoyed the conversations with Georg Grasegger, who also helped me with the computations of Table 3.1 (for the combinatorial algorithm) and explained to me the modifications of the algebraic systems in the absence of a triangle in d = 3 (which is generalized in Appendix B).

I would also like to thank my parents Kostas (που θα ήθελε να ήταν εδώ) and Athina for their continuous affection and support. Last but not least, I want to thank my family, Danai and Iasonas, for their endless patience and love all this time.

LIST OF FIGURES

5.2

Since the lengths of λ u,q and λ u,w are changed accordingly to the length of (u, v) (blued dashed edges), the coupler curves C q,λ ′ (t) and C u ′ ,λ ′ (t) are independent of t. The red dashed edge (u, u ′ ) is removed from G. . . . . .

INTRODUCTION

Rigidity theory is a mathematical area that lies in the intersection of graph theory, compu tational algebra and computational geometry. Although the foundations of rigidity theory can be traced in 19th century, there is nowadays a refreshment of scientific research on this subject motivated by applications in mollecular biology [START_REF] Billinge | Assigned and unassigned distance geometry: applications to biological molecules and nanos tructures[END_REF][START_REF] Gáspár | Rigidity and flexibility of biological networks[END_REF][START_REF] Liberti | On the number of realiza tions of certain Henneberg graphs arising in protein conformation[END_REF] , sensor network localization [START_REF] Zhu | Universal rigidity and edge sparsification for sensor network localization[END_REF], robotics [START_REF] Krick | Stabilisation of infinitesimally rigid forma tions of multirobot networks[END_REF][START_REF] Walter | On a 9bar linkage, its possible configurations and condi tions for paradoxical mobility[END_REF][START_REF] Zelazo | Rigidity main tenance control for multirobot systems[END_REF] and architecture [START_REF] Baglivo | Incidence and Symmetry in Design and Architecture. Cam bridge Urban and Architectural Studies[END_REF][START_REF] Emmerich | Structures Tendues et Autotendantes[END_REF]. Besides these applications, there is active interest in rigidity theory as an independent mathematical subject. One of the major open problems in rigidity theory is to determine tight bounds on the maximal number of embeddings of rigid graphs in an euclidean space or a manifold up to a given number of vertices. In this thesis, we present methods that improve both the asymptotic upper bounds and the asymptotic lower bounds on this maximal number.

Rigidity theory examines the properties of graphs that may have rigid embeddings in a given space. In this thesis, we are interested in embeddings of simple undirected graphs in the euclidean space R d , or the ddimensional sphere S d . If the vertices or the edges of a graph G are not specified, then we denote by V (G) the first and E(G) the latter. Let us present some basic definitions of rigidity theory in this context using the usual euclidean norm. Analogous definitions can be applied for embeddings in other spaces or using other norms [START_REF] Clinch | Constructing isostatic frameworks for the ℓ 1 and ℓ ∞ plane[END_REF][START_REF] Nixon | A characterization of generically rigid frameworks on surfaces of revolution[END_REF][START_REF] Whiteley | Cones, infinity and onestory buildings[END_REF]. Let G = (V, E) be a simple undirected graph (denoted also as G(V, E) or simply G in the rest of the manuscript) and This induced set of edge lengths can be used to define whether a framework is rigid or not. A framework G(ρ) is called rigid if there is only a finite number of embeddings (the term realizations is used equivalently in this context) for graph G that satisfy the edge length constraints imposed by λ up to rigid motions (rotations and translations) 1 . Otherwise, if the number of realizations is infinite up to rigid motions, then G(ρ) is called flexible. Equivalently, rigid frameworks do not admit continuous deformation preserving the edge lengths, while flexible frameworks can be continuously deformed (see Figure 1.1).

ρ = {ρ 1 , ρ 2 , . . . ρ |V | } ∈ R d•|V | be an embedding of G in R d , i.
The embeddings of a graph G(V, E) for a given set of edge lengths λ can be specified as the real solutions of algebraic equations that capture the edge length constraints. The simplest algebraic formulation is to consider the set of squared distance equations

λ 2 u,v = d i=1 (x u,i -x v,i ) 2 , ∀(u, v) ∈ E (1.1)
where x u,i represents the i-th coordinate of vertex u.

The complex solutions of these systems naturally extend the notion of graph embedding in ) to the right one (a 3 ) there is an infinity of realizations up to rigid motions. On the other hand, if an edge is added, then there are only two realizations up to rigid motions and reflections (b 1 and b 2 ) and there is no way to continuously deform this framework. complex spaces, thus the possible configurations of |V | points in C d that satisfy the system of Equations 1.1 are called complex embeddings. Notice that in the case of complex embeddings the system of Equations 1.1 is not relevant with the usual complex norm. Clearly, a graph embedding is either rigid in both R d and C d , or flexible for both cases. We remark that whenever we refer to complex embeddings in the case of the d-dimensional sphere S d , it is the set of the complex solutions of squared distance equations combined with

d+1 i=1 x 2 u,i = 1, ∀u ∈ V (1.2)
and the embedding space shall be denoted S d C . In fact, rigidity in R d (or S d ) is also a generic property of the underlying graph without taking into account the specific embedding [START_REF] Asimow | The rigidity of graphs[END_REF][START_REF] Graver | Combinatorial rigidity, volume 2 of Gradu ate studies in mathematics[END_REF]. In other words a graph is generically rigid if it is rigid for an open dense subset of embeddings ρ ∈ R d•|V | . An important class of generically rigid graphs are the generically minimally rigid graphs. A graph G(V, E) is generically minimally rigid iff G is generically rigid while G -e is flexible, for every e ∈ E. We remark that the classes of generically rigid graphs and generically minimally rigid coincide in R d and S d [START_REF] Whiteley | Cones, infinity and onestory buildings[END_REF]. Additionally, a graph that is generically rigid (or generically minimally rigid) in a real space holds this property for the corresponding complex space.

A milestone theorem in rigidity theory relates a simple edge count with a necessary con dition for minimal rigidity.

Theorem 1 (Maxwell [53])

A simple undirected graph G(V, E) is minimally rigid in R d if |E| = d • |V | -d+1 2 and the inequality |E ′ | ≤ d • |V ′ | -d+1 2 holds for every subgraph G ′ = (V ′ , E ′ ) ⊂ G.
Maxwell's condition corresponds intuitively to the number of vertex coordinates reduced by the number of degrees of freedom (dof) of rigid motions (d for the translations and d 2 for the rotations).

Maxwell's condition is also sufficient in the plane, as proved by G.Laman in the 70s [START_REF] Laman | On graphs and rigidity of plane skeletal structures[END_REF], giving a full characterization for minimally rigid graphs in R 2 . These graphs are wellknown as Laman graphs in the bibliography, while Maxwell's condition is called Laman's condi tion. What was recently found is that this result was originally discovered (but then forgot ten) by H. PollaczekGeiringer [START_REF] Pollaczekgeiringer | Über die Gliederung ebener Fachwerke[END_REF][START_REF] Pollaczekgeiringer | Zur Gliederungstheorie räumlicher Fachwerke[END_REF]. Following [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF], minimally rigid graphs in R 3 will be called Geiringer graphs in this thesis, to honour her legacy. Unlike Laman graphs, there is no full combinatorial characterization of Geiringer graphs and this maybe constitutes the main open problem in rigidity theory. In fact, Maxwell's count fails as a sufficient condition in this case and higher dimensions (see Figure 1.2 for the famous double banana counterexample). The only subclass of Geiringer graphs that is fully characterized are the planar Geiringer graphs (Gauchy's theorem on strictly convex simplicial polyhedra [START_REF] Whiteley | Infinitesimally rigid polyhedra. i. statics of frameworks[END_REF]).

Figure 1.2:

The doublebanana graph is composed by two identical rigid components (blue and green) that are glued to two common vertices. Although this structure satisfies Maxwell's condition in R 3 , it is not rigid: its two rigid components revolve in the space around the implied dashed axis that passes through the common vertices.

Although minimally rigid graphs constitute the main focus of this thesis, we are also con cerned with another important class of rigid graphs. A globally rigid embedding is an embedding that can have a unique realization up to isometries for the same edge lengths. Global rigidity can also be a generic property [START_REF] Jordan | Global rigidity[END_REF] and there is a combinatorial characteri zation for globally rigid graphs in R 2 [START_REF] Connelly | Generic global rigidity[END_REF], but not in higher dimensions. In any dimension, it is possible to check if a generic framework is globally rigid using the rank of stress ma trices of rigidity matroids [START_REF] Gortler | Characterizing generic global rigidity[END_REF]. It is obvious that if a graph G(V, E) is generically globally rigid, then every graph that has the same vertex set and a superset of its edges is also globally rigid.

From an algebraic point of view, Maxwell's condition states that minimally rigid graphs can be related with square algebraic systems, such that no subsystem is overconstrained. In the case of the system of Equations 1.1, this can be achieved by fixing as many coordi nates as the dof of rigid motions for the embedding space. The methods and the results of this thesis rely on the algebraic modelling of the minimally rigid graph embeddings with wellconstrained systems of equations. The main focus is the number of embeddings of specific graphs up to rigid motions, which will be called simply embedding number, and the bounds on this number for graphs with a given number of vertices.

Given a minimally rigid graph G(V, E) in R d and a set of edge lengths λ, r d (G, λ) de notes the embedding number in R d for this specific edge labelling, while r d (G) denotes the maximal finite number of its embeddings for any generic λ ∈ R |E| + . In the case of C d , the embedding number is the same for every generic choice of λ [START_REF] Jackson | Equivalent realisations of a rigid graph[END_REF][START_REF] Sommese | The Numerical Solution of Systems of Polyno mials Arising in Engineering and Science[END_REF] and will be de noted c d (G). It is obvious that c d (G) serves as an upper bound for r d (G). Although these numbers coincide in many cases (see for example [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF][START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF][START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF]), it has been proven that there are examples of a Laman graph such that c d (G) > r d (G) [START_REF] Jackson | Equivalent realisations of a rigid graph[END_REF] . We will also denote with r d (|V |) and c d (|V |) the maximal embedding number over all minimally rigid graphs in R d with |V | vertices in the real and complex case respectively. Finally, for the spheri cal embedding number we will use the notation

r S d (G, λ), r S d (G), c S d (G), r S d (|V |), c S d (|V |)
analogously with the euclidean case.

The main problem treated in the present thesis is to reduce the gap between upper and lower bounds of the embedding number. In the following paragraphs, we will describe the existing work on the field, our contribution and the organization of the text. In an effort to improve the asymptotic upper bound for Laman embeddings, mixed volume techniques have been applied [START_REF] Steffens | Mixed volume techniques for embeddings of Laman graphs[END_REF]. The system of equations used in that case is a mod ified version of Equations 1, which is suitable for sparse elimination2 . This approach did not manage to improve the (trivial) Bézout bound in the general case.

Related work

Another algebraic formulation that computes the embedding number relies on distance ge ometry, since the determinantal varieties of CayleyMenger matrices can be used to spec ify graph embeddings. Applying a theorem on the degree of determinantal varieties [START_REF] Harris | On symmetric and skewsymmetric determinantal varieties[END_REF], the authors in [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF] delivered what used to be the best known upper bound on c d (|V |): .3) which also does not improve asymptotically upon the trivial bound.

2 • |V |-d-2 j=0 |V | -1 + j |V | -d -1 -j 2j + 1 j . ( 1
Besides asymptotic upper bounds, the mixed volume bound has been used for specific graphs, in order to give an estimate for the embedding number [START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF]. Although this is the tightest upper bound [START_REF] Sommese | The Numerical Solution of Systems of Polyno mials Arising in Engineering and Science[END_REF] in general, if the comparison ignores the precise variety where roots lie, its computation is #Phard (by reduction from the permanent).

Remark that there exist also real algebraic bounds [START_REF] Bihan | New fewnomial upper bounds from Gale dual polynomial system[END_REF][START_REF] Khovanskii | Fewnomials, volume 88 of Translations of Mathematical Mono graphs[END_REF] that are sharper than mixed volume and other complex bounds for polynomials which possess suitable structure. In the case of the embedding number, these are by far higher than the (more general) complex bounds.

The computation of exact numbers for c d (G) is more demanding than mixed volume com putation. In the case of Laman graphs there exist combinatorial algorithms that count the embedding number in both C 2 and S 2 C [START_REF] Capco | The number of realizations of a Laman graph[END_REF][START_REF] Gallet | Counting realizations of Laman graphs on the sphere[END_REF], but it is almost infeasible to compute c d (G) for graphs with more than 18 vertices in a desktop computer. Computations for Geiringer embeddings have been even more difficult, since no combinatorial algorithms exist in this case. Gröbner base solvers have been used for these computations [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF], but they may require more than 3 days for a single 11vertex graph.

Finding the maximal number of real embeddings requires repetitive equation solving in an effort to approach the complex embedding number c d (G) with r d (G). This problem demands efficient sampling of the edge length constraints that are considered as param eters of the algebraic system. In rigidity theory, this sampling has been achieved using coupler curves [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF] and stochastic methods [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF], establishing tight bounds for r 2 (6) and r 2 [START_REF] Bartzos | New upper bounds for the number of embed dings of minimally rigid graphs[END_REF] respectively. Let us note that the question of searching for parameters that maximize the real solutions of a given algebraic system is a wellknown problem in real algebraic geometry. One of the most famous cases is the gradient descent method that was used to maximize the number of real StewartGough Platform configurations [START_REF] Dietmaier | The StewartGough platform of general geometry can have 40 real pos tures[END_REF].

Let us now compare the trivial asymptotic upper bound with the existing lower bounds. Asymptotic lower bounds on graph embeddings can be established by gluing frameworks in order to construct arbitrary big rigid graphs [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF][START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. In the bibliography lower bounds have been computed for the cases of Laman and Geiringer graphs. In the case of complex spaces it has been proven that there exist Laman graphs with Ω(2.5079 |V | ) and Ω(3.0683 |V | ) embeddings in C 2 and C 3 respectively [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF], while in the case of spherical embeddings in S 2 C [START_REF] Gallet | Counting realizations of Laman graphs on the sphere[END_REF], while for Geiringer we have that c S 2 (|V |) ∈ Ω(2.5698 |V | ). As for real lower bound, the existing bound on the plane and the space have been Ω(2.3003 |V | ) [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF] and Ω(2.5198 |V | ) [START_REF] Emiris | Computer Algebra Methods for Studying and Computing Molecular Conformations[END_REF][START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF] respectively. A summary of these cases, comparing the existing asymptotic lower and upper, is given in Table 1.1.

Contribution

As presented above the gap between the asymptotic upper bounds and the lower bounds is enormous. In the present thesis we develop methods to compute efficient graphspecific upper bounds on the embedding number and we subsequently reduce the asymptotic upper bound. We also present sampling procedures that increase the lower bounds on the real embedding number. Initially, we propose two methods that compute the multihomogeneous Bézout (mBézout) bound of algebraic systems modeling graph embeddings. These methods apply in both euclidean and spherical cases. The first one relates this bound with the number of outdegreeconstrained graph orientation, based on a standard partition of variables. In this context, we also present a recursive combinatorial algorithm that computes these ori entations. The second one uses the wellknown connection between the computation of matrix permanents and mBézout bounds. For that reason, we demonstrate the construc tion of the (0, 1)matrix that captures the algebraic formulation we use. Then we compare computation runtimes between these two methods and also other algorithms that compute mixed volumes or the exact number of roots for the same algebraic systems.

Regarding the exactness of the bound, we present experimental results that compare m Bézout with mixed volume bounds and the actual number of complex embeddings of all Laman and Geiringer graphs with |V | ≤ 9 vertices, and some selected Laman graphs up to |V | = 18 and Geiringer graphs up to |V | = 12. These results show that the m Bézout is exact for the large majority of spherical embeddings in the case of planar Laman graphs, while it is exact for all planar Geiringer graphs. Motivated by this observation, we adjust Bernstein's discriminant conditions on the exactness of mixed volume to the case of mBézout bounds using Newton Polytopes whose mixed volume equals to the m Bézout. This method shows that an exponential number of conditions is always verified for the specific algebraic systems reducing the number of computations required. Despite this reduction, this number remains exponential, but based on experimental results we conjecture that it can be eventually linear.

In the sequel we make a first attempt to reduce the asymptotic upper bound using existing bounds on the methods described above. Direct application of the best upper bound for orientations [START_REF] Felsner | On the number of planar orientations with prescribed degrees[END_REF] improve the asymptotic upper bound for the subclass of planar Geiringer graphs, while using the BrègmanMinc bound on the permanents of (0, 1)matrices [START_REF] Brègman | Some properties of nonnegative matrices and their permanents[END_REF][START_REF] Minc | Upper bounds for permanents of (0, 1)matrices[END_REF] we were able to decrease the asymptotic upper bound for all minimally rigid graphs in dimensions d ≥ 5.

In order to achieve better bounds, we develop a method bounding recursively the out degree constrained orientations of a minimally rigid graph which is related with the m Bézout bound [START_REF] Bartzos | New upper bounds for the number of embed dings of minimally rigid graphs[END_REF]. For this reason, we introduce a graphical structure, pseudographs, and we relate the orientations of minimally rigid graphs with pseudographs. Finally, we prove that the bound of the recursive method on the orientations of pseudographs improves the bound on the embedding number. More precisely, in the case of Laman graphs the new bound is in the order of O(3.7764 |V | ), while in the case of Geiringer graphs it is O(6.8399 |V | ).

Finally, we also manage to improve lower bounds on the maximal real embedding number in the case of R 2 , R 3 and S 2 [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF]. Our goal is to find the set of edge lengths λ for a graph G, such that the number of real embeddings for this specific set r d (G, λ) would match the number of complex embeddings c d (G), thus maximizing r d (G). Using sphere equations and the CayleyMenger embeddability conditions, we applied some standard methods that sample parameters in order to increase real solutions of algebraic and semialgebraic sys tems (sampling close to nongeneric parameters, stochastic methods, cylindrical algebraic decomposition CAD). Besides these methods, a new algorithm by J.Legerský (coauthor of [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF]) inspired by coupler curves was used to increase the maximal number of embeddings in the spatial case.

These methods lead to a full characterization of all minimally rigid graphs with |V | ≤ 7 up to r d (G) in the cases of R 2 and R 3 , while in the case of S 2 this characterization is achieved for |V | ≤ 6. We also find maximal embedding numbers for selected bigger graphs, leading to new asymptotic lower bounds. More precisely, we prove that there are graphs with Ω(2.

3780 |V | ) embeddings in the case of R 2 , Ω(2.5198 |V | ) embeddings in S 2 and Ω(2.6553 |V | ) in R 3 .
Organization The rest of the thesis is organized as follows. In Chapter 2 we give some preliminaries on the construction of minimally rigid graphs and the algebraic modelling that specifies the embeddings for a given set of edge lengths. More precisely, Henneberg steps are described in Section 2.1. These are used to construct all minimally rigid graphs in a given embedding space. Afterwards, in 2.2 we introduce two algebraic formulations used to count the embedding number. The first one is variation of the squared distance equations between adjacent vertices, that we call sphere equations. The latter uses semi algebraic sets derived from CayleyMenger determinants.

In Chapter 3, we study the mBézout bound of sphere equations. In Section 3.1 we present two methods for its computation and subsequently we compare the runtimes of these methods with existing computational ones that compute mixed volumes and the embed ding number. In Section 3.2 we study the exactness of this bound. First we present experimental results indicating that the bound is tight for certain classes of minimally rigid graphs. Then we develop a method that checks whether the mBézout bound is exact, using Bernstein's second theorem on the exactness of mixed volume. The results of this Chapter are part of the joint work with I.Z. Emiris and J. Schicho and have been published in [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF].

In Chapter 4, we present certain approaches that improve existing upper bounds, using the methods presented in the previous chapter. In Section 4.1, we apply existing bounds in our methods that directly improve the asymptotic upper bounds for certain classes of graphs. These results are also part of [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF]. In Section 4.2, we develop a new method that bounds degreeconstrained orientations leading to new upper bounds for minimally rigid graphs in any embedding space in R d or S d . This project is a joint work with I.Z. Emiris and R. Vidunas and its results have been accepted for publication [START_REF] Bartzos | New upper bounds for the number of embed dings of minimally rigid graphs[END_REF].

In Chapter 5, we present the methods that led to new lower bounds on the maximal em bedding number in R 2 , R 3 and S d . These methods rely on efficient sampling of the pa rameter space that maximized the number of real solutions for the embedding number. This Chapter is part of the joint work with I.Z. Emiris, J.Legerský and E.Tsigaridis. A part of this chapter dealing with the spatial embeddings was published in the proceedings of ISSAC 2018 [START_REF] Bartzos | On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs[END_REF], while the totality of the results presented here constitute the subject of a journal publication [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF]. The algorithms for the coupler curve visualization and sampling in the spatial case were created by J.Legerský. The results for the graphs with the maximal embedding number in R 2 were also contributed independently by the same author.

Finally in Chapter 6, we give an overview of the results of the present thesis and open questions motivated by them.

PRELIMINARIES

In this chapter we present some basic concepts about the construction of rigid graphs and the algebraic formulation used to compute the embedding number.

Henneberg construction

In general, Maxwell's condition (Theorem 1) is not suitable to find the set (or a superset) of all minimally rigid graphs with a given number of vertices. • in an H1 move, the vertex added is connected with d existing vertices.

• in an H2 move, an edge is deleted in the existing graph and the added vertex is connected with the vertices of the deleted edge and d -1 more existing vertices (thus the total degree of the added vertex is d + 1).

In all dimensions H1 and H2 steps preserve rigidity and minimal rigidity: if G * is constructed by applying an H1 or an H2 move to a (minimally) rigid graph G, then G * is also (minimally) rigid. Similarly, if G is generically flexible, then an H1 or H2 move also preserves this property.

In the case of d = 2 all minimally rigid graphs can be obtained by H1 and H2 operations, giving one more method to characterize Laman graphs. On the other hand, these two moves are not sufficient to construct all minimally rigid graphs in d ≥ 3, so extended Henneberg steps are required. These give a superset of minimally rigid graphs.

For Geiringer graphs, there is an additional step in which 2 edges are deleted and the new vertex is connected with the the vertices of the deleted edge and 1 more existing vertex. This is known as Henneberg 3 (H3) step (See Figure 2.1 for the 2 versions of this move in the space, i.e. H3x and H3v steps). Let us comment that the Geiringer graphs whose construction requires an H3 move in the last step have minimal degree 5 and no such graph exist for any graph with n ≤ 11 vertices. It is conjectured that H1, H2 and H3 completely characterize rigid graphs in R 3 [START_REF] Schulze | Rigidity and scene analysis[END_REF][START_REF] Tay | Generating isostatic frameworks[END_REF]. However, it has been proven that H3 move does not always preserve rigidity in dimension 4 [START_REF] Maehara | On Graver's Conjecture Concerning the Rigidity Problem of Graphs[END_REF].

We used Henneberg steps to construct sets of Laman and Geiringer graphs up to isomor phism (see Table 2.1), using canonical labeling as in [START_REF] Capco | The number of realizations of a Laman graph[END_REF][START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. Since Henneberg moves add a vertex with a fixed degree, we can separate the sets of graphs with the same num ber of vertices up to their minimal degree. So if a graph in dimension 2 has minimal degree 2, then it can be constructed with an H1 move in the last step. If the minimal degree is 3 it certainly requires an H2 move in the last step of the Henneberg sequence. This di vision is useful because the H1 move trivially doubles the number of embeddings, since the new vertex lies in the intersection of d different (d -1)spheres. This means that we can deduce the embedding number of a graph G in R d with a dvalent vertex v, if we know the embedding number of the graph G -{v}, without computing the number of solu tions of an algebraic system. On the other hand, computations have shown that the effect of other Henneberg steps on the embedding number varies significantly depending on a graph [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. Thus, we will call minimally rigid graphs with a dvalent vertex trivial, while if the degree of the vertices is always bigger or equal than d + 1, the graph shall be called nontrivial.

Algebraic Formulation

We introduce the algebraic formulations that serve to compute the embedding number and bounds on it. Initially, we present an algebraic formulation that is based on a variant of the squared distance equations 1.1. This formulation has been used several times in the context of studies on rigid graphs that exploit sparse elimination techniques [START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF][START_REF] Steffens | Mixed volume techniques for embeddings of Laman graphs[END_REF]. Subsequently, we present the CayleyMenger embeddability conditions that are related with the vanishing or the sign of certain determinants of a distance matrix.

Sphere equations

The basis of the first formulation are the squared distance equations. In order to compute the embedding number using such system we need to remove rigid motions by fixing

d+1 2
coordinates yielding a 0-dimensional system. In the case of dimension 2, we may fix both coordinates of one vertex and one coordinate of a second vertex. If these vertices are adjacent to one edge, then the length constraint imposes only one solution for the remaining coordinate of the second vertex up to rotations. In general, if the graph contains a complete subgraph with d vertices v 1 , v 2 , . . . v d , then we can choose the coordinates of this K d graph in a way that they satisfy the edge lengths of this subgraph. These shall be the fixed vertices, while K d will be also called fixed. The number of (real) solutions of the system with the fixed vertices will give the (real) embedding number of the graph for a specific edge labelling. So, in the case of Laman graphs, we need to fix an edge, while in 3 dimensions a triangle should be fixed. Note that for the first set of graphs there is always a K 2 (edge). As for the 3dimensional case, Geiringer graphs with no triangles (K 3 ) are very rare (the first one is the 10vertex complete bipartite graph K 6,4 )2 .

We will transform the squared distance equations to fit some requirements of sparse elim ination, using an algebraic system with two sets of equations. First we define the set of magnitude equations that introduce new variables representing the distance of each ver tex from the origin. Substituting the new variables to the squared distance equations, we get the edge equations, which represent the edge length constraints between the adjacent vertices of an edge. The algebraic system derived from the combination of these two sets shall be called sphere equations.

Definition 1 Let G(V, E) be a simple undirected graph. We denote by λ

= {λ u,v | (u, v) ∈
E} the set of the (given) edge lengths and by X u = {x u,1 , x u,2 , . . . x u,d } the variables as signed to the coordinates of each vertex. The following system of equations gives the embeddings of G:

X u 2 = s u , ∀ u ∈ V \V (K d ) , s u + s v -2 X u , X v = λ 2 u,v , ∀ (u, v) ∈ E\E(K d ) , (2.1)
where X u , X v is the Euclidean inner product. We will denote the set of variables X u = X u {s u } in the euclidean case using s u as the (d + 1)th variable x u,d+1 . If a vertex is fixed, its variables are substituted with constant values. This formulation can be obviously used in the case of embeddings on the unit ddimensional sphere S d using |X u | = d + 1 coordinates and setting s u = 1.

This algebraic system has

m = d•|V |-d 2 edge equations and |V |-d magnitude equations if there is at least one subgraph K d of G.
Notice that the edges of the fixed K d serve to specify the fixed vertices and are not included in this set of equations, so m < |E|. We will denote the set of the complex solutions for this algebraic system S(G, λ,

K d (ρ)) ⊂ C d•|V |
for a given embedding ρ of a complete graph K d satisfying the edge length constraints and the set of real solutions S R (G, λ,

K d (ρ)) = S(G, λ, K d (ρ)) ∩ R d•|V | for the same embedding of K d . Clearly c d (G) = |S(G, λ, K d (ρ))| for any generic set of lenghts λ, while r d (G, λ) = |S R (G, λ, K d (ρ))|.
Notice that both c d (G) and r d (G, λ) are independent of the choice for a fixed K d .

CayleyMenger determinants

A CayleyMenger (CM) matrix is a matrix of squared distances between n points in an Euclidean space extended by a row and column of ones:

CM =       0 1 1 • • • 1 1 0 λ 2 1,2 • • • λ 2 1,n 1 λ 2 1,2 0 . . . . . . • • • • • • . . . . . . . . . 1 λ 2 1,n λ 2 2,n • • • 0      
, where λ i,j is the distance between point i and j.

One of the main theorems in distance geometry gives the following embeddability condi tions for a CM matrix [START_REF] Blumenthal | Congruent Imbedding in Euclidean Space[END_REF]:

Theorem 2 The squared distances of a CM matrix can be embedded in R d iff • rank(CM ) = d + 2
• (-1) κ det(CM ′ ) ≥ 0, for every submatrix CM ′ with size κ + 1 ≤ d + 2 that includes the extending row/column.

In the case of graph embeddings, we can use a matrix with known entries and variables: each known entry corresponds to a squared edge length, while the variables correspond to lengths between nonedges. This results to a system of determinantal equations and inequalities. Any solution of the semialgebraic system is an embedding of the graph in R d up to isometries, indicating that each one of these solutions correspond to 2 solutions in the case of sphere equations since reflections are factored out in this formulation.

Considering only the solutions of the determinantal variety, we get the complex embed dings of the graph. The set of inequalities is related with certain geometrical constraints on the edge lengths, such as positivity and triangular inequalities in dimension 2. In di mension 3, tetrangular inequalities (which are a generalization of triangular inequalities on the area of the triangles of a tetrahedron) should be also satisfied, while in bigger dimen sions there are additional constraints (in this thesis only dimensions 2 and 3 are taken into consideration with this algebraic formulation) [START_REF] Dattorro | Euclidean Distance Matrix[END_REF].

The systems of equations of determinantal varieties are overconstrained. For exam ple, there are 35 equations in 10 variables for 7vertex Laman graphs, while for 7vertex Geiringer graphs, there are 21 equations in 6 variables. Despite this fact, it is possible to find 0dimensional square subsystems of these systems of equations [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF][START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF].

Notice that the zero set of the whole determinantal variety corresponds to the missing edge lengths of the complete graph. This means that the solutions of the subsystem are restricted to a subset of the missing edge lengths. If the graph extended by the edges corresponding to the variables of the subsystem is globally rigid, then the subsystem gives an upper bound on the number of embeddings of the whole graph [START_REF] Jackson | Equivalent Realisations of Rigid Graphs[END_REF], since globally rigid graphs have unique realizations (see Chapter 1).

In the cases treated in Chapter 5, square subsystems can be easily detected, if no re striction is imposed on the number of variables. Unfortunately, these subsystems are not always 0dimensional and cannot serve to find the embedding number of a graph or a use ful upper bound. Nevertheless, our experimental results lead to the conclusion that there can be subsystems derived from a graph G(V, E) with |V |-(d+1) equations satisfying the 0dimensionality condition. For the most important cases, we show that for dimensions 2 and 3 there is always an extension of a minimally rigid graph with |V | -(d + 1) edges resulting to a globally rigid graph.

Lemma 1 For every minimally rigid graph

G(V, E) in dimensions d = 2 and d = 3, there is at least one extended graph J = G ∪ {e 1 , e 2 , .., e ξ }, with ξ = |V | -(d + 1
) and e i / ∈ E, which is globally rigid in R d .

Proof:

The only 4vertex minimally rigid graph in dimension 2 (respectively 5vertex in dimension 3) is obtained by applying an H1 step to the triangle (resp. tetrahedron in di mension 3). If we extend this graph with the only nonexisting edge, we obtain a complete graph, so the lemma holds. Let the lemma hold for every graph that has less or equal ver tices with G |V | = (V, E). H2 steps are known to preserve global rigidity in any dimension [START_REF] Connelly | Generic global rigidity[END_REF]. So we need to prove the induction for H1 steps in both dimensions and H3 steps in dimension 3. ). This is equivalent with applying an H2 step and adding the deleted edge (u, v |V |+1 ).

v 1 v 2 u v |V |+1 v 1 v 2 v 3 u v |V |+1 R 2 R 3
connects a new vertex v |V |+1 with vertices v 1 , v 2 . Let u be a neighbour of v 1 in G |V |+1 such that v 2 = u. The edge (u, v 1 ) exists also in G |V | and J |V | . If we set J ′ |V |+1 = (J |V | ∪ {(v 1 , v |V |+1 ), (v 2 , v |V |+1 ), (u, v |V |+1 )}) -{(v 1 , u)}, then J ′ |V |+1 is globally rigid, because it is constructed from J |V | by an H2 step. Hence, J |V |+1 = J ′ |V |+1 ∪ {(u, v 1 )
} is also globally rigid, proving the statement in the case of H1 steps in dimension 2. The same result holds in arbitrary dimension (see Figure 2.2 for d = 3).

Both H3x and H3v steps consist of an H2 step followed by a second edge deletion in the existing graph and a new connection with v |V |+1 (see Figure 2.1). So, if we apply an H3 move in J |V | and subsequently add the second deleted edge, then J |V |+1 is globally rigid. □ Even though, there are always globally rigid extentions with |V | -(d + 1) supplementary edges, it is not always possible to find a CM subvariety corresponding to them. Such subvarieties can be detected for all Laman and Geiringer graphs with |V | ≤ 7 vertices, but there exist bigger graphs for which this property does not hold.

v 1 v 2 v 3 v 4 v 5 v 6 v 7

Figure 2.3:

The embeddings of the Laman graph L 48H2 (grey edges) can be represented by submatrices of CM L 48H2 that involve only variables corresponding to the 4 red dashed edges. The extended graph is globally rigid. This construction can be used to find also the spherical embeddings.

We now give some representative examples of optimal CM subsystems in the cases of E. Bartzos Laman and Geiringer that are used to find lower bounds in Chapter 5. For instance, L 48H2 is a 7vertex Laman graph (see Figure 2.3), which has c 2 (L 48H2 ) = r 2 (L 48H2 ) = 48 and c S 2 (L 48H2 ) = r S 2 (L 48H2 ) = 64 (See Section 5.2). There are 11 subsystems of this CM variety in 4 variables, which all have exactly the same number of solutions. In the following CM matrix, we present one of these choices involving the variables x 1 , x 2 , x 6 and x 7 .

CM L 48H2 =             0 1 1 1 1 1 1 1 1 0 λ 2 v 1 ,v 2 x 1 λ 2 v 1 ,v 4 x 2 λ 2 v 1 ,v 6 λ 2 v 1 ,v 7 1 λ 2 v 1 ,v 2 0 λ 2 v 2 ,v 3 x 3 λ 2 v 2 ,v 5 x 4 x 5 1 x 1 λ 2 v 2 ,v 3 0 λ 2 v 3 ,v 4 λ 2 v 3 ,v 5 x 6 x 7 1 λ 2 v 1 ,v 4 x 3 λ 2 v 3 ,v 4 0 x 8 x 9 λ 2 v 4 ,v 7 1 x 2 λ 2 v 2 ,v 5 λ 2 v 3 ,v 5 x 8 0 λ 2 v 5 ,v 6 x 10 1 λ 2 v 1 ,v 6 x 4 x 6 x 9 λ 2 v 5 ,v 6 0 λ v 6 ,v 7 1 λ 2 v 1 ,v 7 x 5 x 7 λ 2 v 4 ,v 7 x 10 λ v 6 ,v 7 0            
In order to compute r 2 (L 48H2 ), the positive real solutions of the determinantal variety should also satisfy the triangular inequalities.

The same extended graph is used to compute the spherical embeddings of L 48H2 . An additional constraint is needed in that case, which represents the distance from the origin, as a new column and row with ones. The determinantal subsystem is derived from the rank condition of 3dimensional embeddings. Elementary matrix operations can lead to a formulation that considers the cosines of the angles between two points as matrix entries, denoted as

η v i ,v j . CM S 2 (L 48H2 ) =               0 1 1 1 1 1 1 1 1 1 0 λ 2 v 1 ,v 2 x 1 λ 2 v 1 ,v 4 x 2 λ 2 v 1 ,v 6 λ 2 v 1 ,v 7 1 1 λ 2 v 1 ,v 2 0 λ 2 v 2 ,v 3 x 3 λ 2 v 2 ,v 5 x 4 x 5 1 1 x 1 λ 2 v 2 ,v 3 0 λ 2 v 3 ,v 4 λ 2 v 3 ,v 5 x 6 x 7 1 1 λ 2 v 1 ,v 4 x 3 λ 2 v 3 ,v 4 0 x 8 x 9 λ 2 v 4 ,v 7 1 1 x 2 λ 2 v 2 ,v 5 λ 2 v 3 ,v 5 x 8 0 λ 2 v 5 ,v 6 x 10 1 1 λ 2 v 1 ,v 6 x 4 x 6 x 9 λ 2 v 5 ,v 6 0 λ v 6 ,v 7 1 1 λ 2 v 1 ,v 7 x 5 x 7 λ 2 v 4 ,v 7 x 10 λ v 6 ,v 7 0 1 1 1 1 1 1 1 1 1 0               ∼               0 1 1 1 1 1 1 1 2 1 0 η v 1 ,v 2 y 1 η v 1 ,v 4 y 2 η v 1 ,v 6 η v 1 ,v 7 1 1 η v 1 ,v 2 0 η v 2 ,v 3 y 3 η v 2 ,v 5 y 4 y 5 1 1 y 1 η v 2 ,v 3 0 η v 3 ,v 4 η v 3 ,v 5 y 6 y 7 1 1 η v 1 ,v 4 y 3 η v 3 ,v 4 0 y 8 y 9 η v 4 ,v 7 1 1 y 2 η v 2 ,v 5 η v 3 ,v 5 y 8 0 η v 5 ,v 6 y 10 1 1 η v 1 ,v 6 y 4 y 6 y 9 η v 5 ,v 6 0 η v 6 ,v 7 1 1 η v 1 ,v 7 y 5 y 7 η v 4 ,v 7 y 10 η v 6 ,v 7 0 1 -2 1 1 1 1 1 1 1 0              
The semialgebraic conditions of the latter formulation, requires that any solution of the determinantal subsystem lies in the interval [-1, 1] and that the triangular inequalities on the sphere are satisfied. The second is equivalent to the positivity of

2η v i ,v j η v i ,v k η v j ,v k - η 2 v i ,v j -η 2 v i ,v k -η 2 v j ,v k +1 for 3 point of vertex embeddings v i , v j , v k
on the sphere, where η v i ,v j is the cosine of the angle between points i and j and can be obtained as the determinant of a 5x5 submatrix containing both columns and rows with ones.

Our example in the 3dimensional case is the graph G 48 (see Figure 2.4). This graph has the maximal number of embeddings among all 7vertex Geiringer graphs (c 3 (G 48 ) = r 3 (G 48 ) = 48 see Section 5.2). There are 5 different square systems in 3 variables that completely define the embeddings. We can choose one of them involving only x 1 , x 2 , x 3 :

CM G 48 =             0 1 1 1 1 1 1 1 1 0 λ 2 v 1 ,v 2 λ 2 v 1 ,v 3 λ 2 v 1 ,v 4 λ 2 v 1 ,v 5 λ 2 v 1 ,v 6 x 1 1 λ 2 v 1 ,v 2 0 λ 2 v 2 ,v 3 x 2 x 3 λ 2 v 2 ,v 6 λ 2 v 2 ,v 7 1 λ 2 v 1 ,v 3 λ 2 v 2 ,v 3 0 λ 2 v 3 ,v 4 x 4 x 5 λ 2 v 3 ,v 7 1 λ 2 v 1 ,v 4 x 2 λ 2 v 3 ,v 4 0 λ 2 v 4 ,v 5 x 6 λ 2 v 4 ,v 7 1 λ 2 v 1 ,v 5 x 3 x 4 λ 2 v 4 ,v 5 0 λ 2 v 5 ,v 6 λ 2 v 5 ,v 7 1 λ 2 v 1 ,v 6 λ 2 v 2 ,v 6 x 5 x 6 λ 2 v 5 ,v 6 0 λ 2 v 6 ,v 7 1 x 1 λ 2 v 2 ,v 7 λ 2 v 3 ,v 7 λ 2 v 4 ,v 7 λ 2 v 5 ,v 7 λ 2 v 6 ,v 5 0            
The set of real embeddings in that case is given by the solutions of the subsystem that satisfy positivity, triangular and tetrangular inequalities.

Extending this graph with the edge (v 1 , v 7 ) suffices for global rigidity. This edge corre sponds to the variable x 1 and it is possible to get a single equation by applying resultants in the 3x3 system of determinantal equations (see Figure 2.4).

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 1 v 2 v 3 v 4 v 5 v 6 v 7 x 1

Figure 2.4: The graph G 48 (grey edges). There are submatrices of CM G 48 that involve only variables corresponding to the 3 red dashed edges of the left graph. The graph G 48

extended by the edge v 1 v 7 (that corresponds to the variable x 1 ) is globally rigid.

Since a single edge is needed to find the whole embedding, we can use only the inequalities involving only this variable (5 triangular and 5 tetrangular inequalities instead of 35 that involve all variables).

ON THE MULTIHOMOGENEOUS BÉZOUT BOUND OF THE EMBEDDING NUMBER

In this chapter we are concerned with the mBézout bound of the sphere equations (see Definition 1). In Section 3.1 we propose two methods for computing the mBézout bound. The first one is a combinatorial method relating outdegree constrained graph orientations with this bound. The latter uses a standard formulation via matrix permanents. We also compare the runtimes of these methods with the runtimes of algorithms that compute mixed volumes and the embedding number.

In Section 3.2, we examine the exactness of mBézout bounds. Initially, we present exper imental results that compare these bounds with embedding numbers and mixed volumes. Then, we present a general method to decide if the mBézout bound of a minimally rigid graph is tight or not without directly computing the embeddings.

All the results of this chapter have been published in [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF].

Computing mBézout bounds

In this section, we concentrate on the mBézout bound of the sphere equations of a graph G(V, E) up to a fixed complete subgraph K d . Let us remind that K d may not be a subgraph of a minimally rigid graph for d ≥ 3. We will give details on the computation of the bound in the absence of K d in Appendix B. For the rest of this chapter, unless further specified, K d will denote a given complete subgraph and not all possible choices.

In order to compute the mBézout bound we will choose a natural partition such that each subset of variables X u contains these ones which correspond to the coordinates and the magnitude of a single vertex u. We will separate the magnitude equations from the edge equations, since the first ones there is only one set of variables with degree 2, while in every edge equation the degree of the uth set of variables is always 1, resulting to the following expansion:

u∈V ′ 2 • Y u (u,v)∈E ′ (Y u + Y v ) = 2 |V |-d • u∈V ′ Y u (u,v)∈E ′ (Y u + Y v ),
where

V ′ = V \ V (K d ), E ′ = E \ E(K d ) and Y u are symbolic parameters representing X u . We remark that if v ∈ V (K d ) and (u, v) ∈ E ′ , then Y v = 0,
(u,v)∈E ′ (Y u + Y v ) (3.1)
Let us denote this coefficient by B(G, K d ), which is related only to the combinatorial struc ture of edge equations. The mBézout bound for the number of embeddings of a graph in

C d up to a fixed K d is mBe(G, K d ) = 2 |V |-d • B(G, K d ).
Notice that this bound is the same for spherical embeddings in S d C . We remark that although c d (G) is invariant under different choices of fixed K d , the m Bézout bound of a graph G may vary up to this choice. Thus, one needs to compute mBézout bounds up to all fixed complete subgraphs in order to find the minimal one. The same observation holds for the BKK bound of sphere equations.

We will use graph orientations and matrix permanents to compute the bound based on the expansion of Equation 3.1. Let us mention that matrix permanents have been already used to bound the number of Eulerian orientations (which are graph orientations with equal indegree and outdegree for every vertex) in [START_REF] Schrijver | Bounds on the number of eulerian orientations[END_REF], but to the best of our knowledge there are no published results on the connection between matrix permanents and outdegree constrained graph orientations in the general case.

A combinatorial algorithm to compute mBézout bounds

This subsection focuses on a method relating mBézout bounds for minimally rigid graphs with graph orientations. Our method is inspired by two different approaches that charac terize Laman graphs. First, Recski's theorem states that if a graph is Laman then any multigraph obtained by doubling an edge should be the union of two spanning trees [START_REF] Schulze | Rigidity and scene analysis[END_REF]. Additionally, pebble games give a relation between the existence of an orientation and the number of constraints in a graph and its subgraphs [START_REF] Lee | Pebble game algorithms and sparse graphs[END_REF]. The following theorem gives a combinatorial method to compute the mBézout bound, proving that mBe(G, K d ) is ex actly the number of certain outdegreeconstrained orientations. These orientations shall be called valid orientations.

In the following theorem E ′ is the same as in Equation 3.1.

Theorem 3

Let G(V, E) be a minimally rigid graph in C d that contains at least one com plete subgraph with d vertices. Let {v 1 , . . . v d } be the vertex set of such subgraph which is the fixed K d . By removing the edges of

K d from G, graph G ′ = (V, E ′ ) is defined. Then B(G, K d ) defined above is the number of outdegreeconstrained orientations denote the of G ′ , such that • the outdegree of v 1 , . . . , v d is 0. • the outdegree of every vertex in V \{v 1 , . . . , v d } is d. Proof: By expanding the product (u,v)∈E ′ (Y u + Y v ), the monomial u∈V ′ Y d
u can be obtained when each Y u from a given edge contributes exactly d times in that product. This means that every time we shall choose one of the two sets of variables that correspond to the adjacent vertices of the edge represented in the parenthesis. This choice yields an orien tation in the directed graph and vice versa. Thus, the number of different orientations in all edges gives us how many times this monomial will appear in the expansion, completing the proof. □

(u, v) ∈ E do 11 outdeg[v] = outdeg[v] -1 12 E ′ =E\{(u, v)} 13 newdeg =vertex degree of graph G ′ (V, E ′ ) 14 return (orient(|V |, Enew, outdeg, newdeg)) else if outdeg[u] = deg[u]
// u admits only new outdirerected edge orientations then for all edges (u, v)

∈ E do 18 outdeg [u] = outdeg [u] -1 19 E ′ =E\{(u, v)} 20 newdeg =vertex degrees of graph G ′ (V, E ′ ) 21 return (orient(|V |, E ′ , outdeg, newdeg))
/* No more unique orientations exists: set both orientations for 1st edge

*/ (u, v) = E [1] outdeg1 [u] = outdeg [u] -1 outdeg2 [v] = outdeg [v] -1 E ′ =E\{(u, v)} newdeg =vertex degree of graph G ′ (V, E ′ ) orient1=orient(|V |, E ′ , outdeg1, newdeg) orient2=orient(|V |, E ′ , outdeg2, newdeg) return (orient1+orient2)
This theorem gives another way to prove that an H1 move doubles the mBézout bound of minimally rigid graphs. Hence, minimally rigid graphs constructed only by H1 moves have at most 2 |V |-d embeddings (actually this bound is tight, see Section 2.1).

Corollary 1 An H1 move always doubles the mBézout bound up to the same fixed K d . Moreover, if a graph can be constructed only with H1 moves, then the mBézout bound for this graph is exactly 2 |V |-d .

Proof: Let B(G, K d ) be the number of outdegreeconstrained orientations for a graph G(V, E) up to a given K d . This means that the mBézout bound is

mBe(G, K d ) = 2 |V |-d • B(G, K d ).
Now, let G * be a graph obtained by an H1move on the graph G. Since H1 adds a degreed vertex to G, this means that there is only one way to reach outdegree d for the new vertex of G * . So the outdegreeconstrained orientations of G * up to the same

K d are exactly B(G, K d ) and mBe(G * , K d ) = 2 |V |+1-d • B(G, K d ) = 2 • mBe(G, K d ).
The second statement of this corollary can be proven using the previous equality: starting from K d , only one orientation satisfies the requirements of Theorem 3 for each H1 move. So, the mBézout bound of a minimally graph constructed only by H1 moves is We have implemented a software tool in Python to count the number of orientations for an arbitrary graph given the desired outdegrees. The basic part of this code (see Algorithm 1) is to decide recursively which choices of direction are allowed in every step and is available in zenodo [START_REF] Bartzos | Source code and examples for the paper[END_REF].

Computing mBézout bounds using the permanent

The permanent of an m × m matrix A = (a i,j ) is defined as follows:

per(A) = σ∈Sm m i=1 a i,σ(i) , (3.2)
where S m denotes the group of all permutations of m integers.

One of the most efficient ways to compute the permanent is by using Ryser's formula [START_REF] Van Lint | A Course in Combinatorics[END_REF]:

per(A) = M ⊆{1,2,...,m} (-1) m-|M | m i=1 j∈M a i,j . (3.3)
There is a very relevant relation between per(A) and the mBézout bound, see [START_REF] Ioannis | Root counts of semimixed systems, and an application to counting nash equilibria[END_REF]:

Theorem 4 Given a system of algebraic equations and a partition of the variables in k subsets, as in Theorem 15, we define the square matrix A with m = n j=1 m j rows, where each set of variables corresponds to a block of m j rows. Let a i,j be the degree of the ith equation in the jth set of variables. The columns of A correspond to the equations, where the subvector of the ith column associated to the jth set of variables has m j entries, all equal to a i,j . Then, the mBézout bound of the given system is equal to

1 m 1 ! m 2 ! • • • m n ! • per(A). (3.4)
We will refer to A matrix as the mBézout matrix of a polynomial system. This implies that in the case of minimally rigid graphs, we obtain a square mBézout matrix A with columns associated to the equations of nonfixed edges, and |V |-d blocks of d rows each, corresponding to the nonfixed vertices. An entry a i,j is one if the vertex corresponding to i is adjacent to the edge corresponding to the equation indexing j, otherwise it is zero. This is an instance of a (0, 1)permanent. Therefore Theorem 4 gives the coefficient

B(G, K d ) = 1 d! |V |-d
• per(A), in bounding the system's roots, since all

m i = d, while n = |V | -d.
Including the effect of magnitude equations the corollary below follows.

Corollary 2

The mBézout bound of the sphere equations for an |V |vertex rigid graph in

d dimensions up to a given K d is exactly mBe(G, K d ) = 2 d! |V |-d • per(A), (3.5)
assuming that matrix A is the mBézout matrix up to K d defined as above.

The permanent formulation for the computation of the mBézout bound gives us another way to prove Corollary 1.

Corollary 3

Let G be a minimally rigid graph in C d and A G be its (m × m) mBézout matrix up to a fixed K d . Then, for every graph G * obtained by an H1 operation on G, the permanent of its mBézout matrix A G * up to the same

K d is per(A G * ) = d! • per(A G ).
Proof: Without loss of generality, we consider that the last d rows of matrix A G * represent the new vertex, while the last d columns of this matrix represent the edges adjacent to this vertex, since matrix permanent is invariant under row or column permutations. The rest of the matrix is the same as A G . This yields the following structure:

A G * = A G A ′ 0 1
where

0 is a (d × m) zero submatrix, 1 is a (d × d) submatrix with ones and A ′ the (m × d)
submatrix of the new edge columns without the new rows. It is clear from the definition of the permanent (See Equation 3.2), that column permutations that do not include a zero entry are counted as 1 in this sum, while if they include a zero entry the product is zero.

The only column permutations that do not include a zero entry for the d last rows are those that are related to the d last edges, so there are d! nonzero column permutations for this block of rows.

This means that the permutations for the other m rows exclude the last three columns, so they are exactly per(A G ) permutations in this case. Thus, per(

A G * ) = d! • per(A G ). □ Since mBe(G * , K d ) = 2 d! |V |+1-d • per(A G * ), it follows that mBe(G * , K d ) = 2 • mBe(G, K d ),
as in Corollary 1.

Let us give an example of this counting method for a minimally rigid graph.

Example 2

We use the L 136 graph to provide an example for this formulation (see Fig ure 3.2 other examples can be found in [START_REF] Bartzos | Source code and examples for the paper[END_REF]). L 136 is the 8vertex Laman graph with the maximal embedding number c 2 (G) = 136 among all Laman graphs with the same number of vertices [START_REF] Capco | The number of realizations of a Laman graph[END_REF]. On S 2 , it has 192 complex embeddings, which is also maximum (but not unique), since there is another graph sharing the same c S 2 (G).

The mBézout matrix A L 136 for this graph for the fixed edge (v 1 , v 2 ) is the following:

(v 1 , v 4 ) (v 1 , v 8 ) (v 2 , v 3 ) (v 2 , v 5 ) (v 2 , v 7 ) (v 3 , v 4 ) (v 3 , v 5 ) (v 4 , v 6 ) (v 4 , v 8 ) (v 5 , v 6 ) (v 6 , v 7 ) (v , v 8 ) x 3 0 0 1 0 0 1 1 0 0 0 0 y 3 0 0 1 0 0 1 1 0 0 0 0 x 4 1 0 0 0 0 1 0 1 1 0 0 y 4 1 0 0 0 0 1 0 1 1 0 0 x 5 0 0 0 1 0 0 1 0 0 1 0 y 5 0 0 0 1 0 0 1 0 0 1 0 x 6 0 0 0 0 0 0 0 1 0 1 1 y 6 0 0 0 0 0 0 0 1 0 1 1 x 7 0 0 0 0 1 0 0 0 0 0 1 y 7 0 0 0 0 1 0 0 0 0 0 1 x 8 0 1 0 0 0 0 0 0 1 0 0 y 8 0 1 0 0 0 0 0 0 1 0 0
and its permanent is per(A L 136 ) = 192, which gives the mBézout bound since d = 2.

1 v 1 2 v 2 3 v 3 4 v 4 5 v 5 6 v 6 7 v 7 8 v 8

Figure 3.2:

The L 136 graph. The dashed edge is the fixed one.

Runtimes

The computation of the mBézout bounds using our combinatorial algorithm up to a fixed K d is much faster than the computation of mixed volume and complex embeddings. In order to compute the mixed volume we used phcpy in SageMath [START_REF] Verschelde | Modernizing PHCpack through phcpy[END_REF] and we computed complex solutions of the sphere equations using phcpy and and MonodromySolver [START_REF] Duff | Solving polyno mial systems via homotopy continuation and monodromy[END_REF]. Let us notice that, MonodromySolver seems to be faster than mixed volume software we used in the case of Geiringer graphs. We also compared our runtimes with the combinatorial algorithm that counts the exact number of complex embeddings in C 2 [START_REF] Capco | The number of realizations of a Laman graph[END_REF].

We will try to give some indicative cases for which we compared the runtimes. For exam ple, computing the mixed volume of the spherical embeddings up to one fixed edge for the maximal 12vertex Laman graph for a given fixed K 2 takes around 390ms, while our algorithm for the mBézout bound required 13ms. If we wanted to compute mixed volumes up to all fixed K 2 we needed 8.6s, while the mBézout computation took 270ms. The run time for the combinatorial algorithm that computes the number of complex embeddings is 6.363s for the same graph.

For larger graphs i.e. 18vertex graphs, the combinatorial algorithm may take ∼ 17h to compute the number of complex embeddings in C 2 . We tested a 18vertex graph that did not require more than 0.12s to compute one mBézout bound and 4s to compute mBézout bounds up to all choices of fixed edges.

In dimension 3 our model was the icosahedron graph, which has 12 vertices. The com putation of the mixed volume took more than 6 days in this case, while our algorithm needed 60ms to give exactly the same result [START_REF] Minc | Upper bounds for permanents of (0, 1)matrices[END_REF]272). MonodromySolver could track all 54, 272 solutions in ∼ 1.3 hour, while Gröbner basis computations failed multiple times to terminate.

Computing the permanent required more time compared to our algorithm. For the icosahedron the fastest computation could be done using Maple's implementation in LinearAlgebra package. It took ∼ 0.96s to compute the permanent up to a given fixed triangle with this one. On the other hand the implementations in Python and Sage took much more time for the same graph (∼ 8m and ∼ 10m respectively). This seems reasonable since if the total number of edge equations is m, then the combi natorial algorithm has to check at most 2 m cases, while according to [START_REF] Ioannis | Root counts of semimixed systems, and an application to counting nash equilibria[END_REF] the complexity to compute the permanent using Ryser's formula is in the order of m 2 • 2 m .

On the exactness of mBézout bounds

In this section we present experimental results and a general method that study the ex actness of the mBézout bound. Our computations use already published results on the embedding number [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF] in order to compare the mBézout bound with it. We also use computations from [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF] (we remind that Chapter 5 is dedicated to the results of this publica tion) on the mixed volumes of sphere equations systems. All the other computations are [START_REF] Capco | The number of realizations of a Laman graph[END_REF] and c 3 (G) by phcpy [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF] (fails to find all solutions for |V | > 11). Also runtimes for computing c 2 (G), c 3 (G) by MonodromySolver. We compute mixed volume (MV) by phcpy, mBézout (mBe) by Maple's permanent and our Python code [START_REF] Bartzos | Source code and examples for the paper[END_REF]. Computation of the m Bézout and MV is up to a fixed K d (edges or triangles). part of this project (mBézout, spherical embeddings and some cases of graphs for which there was no information on their embedding number). These results show that there are some classes that the mBézout is a tight bound.

Laman graphs

We also develop a method based on Bernstein's second theorem on the exactness of the mixed volume bound [START_REF] Bernstein | The number of roots of a system of equations[END_REF]. Our main goal is to reduce the number of checks on the Minkowski sum of Newton Polytopes that are required by this theorem. We consider that this method may be a first step to establish the existence of classes of graphs with tight mBézout bounds.

Experimental results

We compared mBézout bounds with the number of embeddings and mixed volumes using existing results [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF][START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF] for the embeddings in C 2 and C 3 . We also computed the complex solutions of the equations that count embeddings on S 2 for all Laman graphs up to 8 vertices and a selection of graphs with up to 12 vertices that have a large number of embeddings. We remind that in general the mBézout bound is not unique up to all choices of a fixed K d . It is natural to consider the minimal mBézout bound as the optimal upper bound of the embeddings for a given graph. Let us notice that we checked if the mBézout is minimized when the fixed K d has a maximal sum of vertex degrees or when the vertex with the maximum degree belongs to the fixed K d . There are counterexamples for both of these hypotheses.

Mixed volume and mBézout bound.

In all cases we checked in C 3 and S 2 , the m Bézout bound up to a fixed K d is exactly the same as the mixed volume up to the same fixed vertices. There are some cases in C 2 for which the mBézout bound is bigger than the mixed volume for certain choices of K 2 . We shall notice that these cases do not correspond to the minimal mBézout bound for the given graph (thus the minimum m Bézout and the minimum mixed volume are the same for these graphs).

Spatial embeddings and the mBézout bound.

There are many Geiringer graphs for which the bound of the sphere equations is larger than the actual number of complex embeddings. Nevertheless, we observed that for all planar graphs (in the graphtheoretical sense) up to |V | = 11 the number of complex embeddings is exactly the same as the mixed volume bound and therefore the mBézout bound, while in the nonplanar case the bounds are generally not tight. What is also interesting is that the mBézout bound is invariant for all choices of fixed triangles for all planar Geiringer graphs.

Embeddings of Laman graphs and the mBézout bound. For Laman graphs, the m Bézout bound diverges from the number of actual embeddings in C 2 more than in the case of Geiringer graphs. That happens both for planar and nonplanar graphs. On the other hand the number of spherical embeddings of planar Laman graphs coincides with the

Using Bernstein's second theorem

Our computations indicate that the mBézout bound is tight for almost all planar Laman graphs in S 2 and all planar Geiringer graphs. Therefore, we apply Bernstein's second the orem to establish a method that determines whether this bound is exact (see Appendix A for details on the BKK bound and Bernstein's second theorem Theorems 16 and 17 re spectively). We believe that a generalization of this method may show whether the exper imental results provably hold for certain classes of graphs. In this subsection for reasons of simplicity, in all examples we will use the variables x i , y i , s i and x i , y i , z i for C 2 and S 2 re spectively (instead of the notation x i,1 , • • • x i,d , s i presented in Definition 1). Also m denotes the total number of variables.

The first step in this Section is to use Newton polytopes whose mixed volume equals to the mBézout bound (see for example [START_REF] Sommese | The Numerical Solution of Systems of Polyno mials Arising in Engineering and Science[END_REF]) since they are simpler than the Newton polytopes of the sphere equations.

Definition 2

We set e i = (0, 0, . . . , 1 ith position , . . . , 0) and let T u d be the simplex defined as the convex hull of the set

{0, e d•(u-1)+1 , e d•(u-1)+2 , . . . , e d•(u-1)+d },
where 0 = (0, 0, . . . , 0) is the origin. Let X u be the uth set of variables under a partition of all variables, with set cardinality

d u = | X u |. Then T u
du is the simplex that corresponds to the variables of this set. The mBézout Polytope of a polynomial, with respect to a partition of the variables, is the Minkowski sum of the T u du for all u, such that each simplex is scaled by the degree of the polynomial in X u . For a multihomogeneous system, simplices T u du belong to complementary subspaces. Then, each mBézout Polytope is the Newton polytope of the respective equation. For general systems, our procedure amounts to finding the smallest polytopes that contain the system's Newton polytopes and can be written as Minkowski sum of simplices lying in the complementary subspaces specified by the variable partition.

In the case of rigid graphs in C d , every set of variables has d + 1 elements. Thus, the m Bézout Polytope of the magnitude equations for a vertex u is 2 • T u d+1 , while the mBézout Polytope of the equation for edge (u, v) is T u d+1 +T v d+1 . This implies that the Minkowski sum of the mBézout Polytopes for the sphere equations of a minimally rigid graph G(V, E) is exactly

P G = u∈V ′ (deg(u) + 2) • T u d+1 ,
where deg(u) is the degree of vertex u in the graph and V ′ the set of nonfixed vertices.

In general, it is hard to compute the Minkowski sum of polytopes in high dimension. But in the case of the mBézout Polytopes the following theorem describes the facet normals of P G . where there are d + 1 nonzero entries corresponding to the variables that belong to the uth variable set.

Proof: Since each T u d+1 belongs to a complementary subspace, P G can be seen as the product of polytopes e j in R d+1 . The theorem follows since the normal fan of a product of polytopes is the direct product of the normal fans of each polytope [START_REF] Ziegler | Fans, Arrangements, Zonotopes, and Tilings[END_REF]. □

This theorem yields a method to find the Hrepresentation of P G , in other words the poly tope is described as the intersection of linear halfspaces and the respective equations are given by the theorem. In all cases where M V = mBe, the polytopes P G can be used instead of the Newton Polytopes of the equations.

The verification of Bernstein's second theorem requires a certificate for the existence of roots of face systems (see Definition 10) for every face of P G , where faces range from vertices of dimension 0 to facets of codimension 1. We propose a method that confirms or rejects Bernstein's condition checking a much smaller number of systems based on the form of facet normals. For this, we shall distinguish three cases below.

The normal of a lower dimensional face can be expressed as the vector sum of facet normals, whose cardinality actually equals the face codimension. This means that we need to verify normals distinguished in the following three cases:

1. vector sums of one or more "coordinate" normals e i 's, 2. vector sums of one or more "noncoordinate" normals δ u 's, 3. "mixed" vector sums containing both e i 's and δ u 's.

Notice that since there are (d + 2) • (|V | -d) different normals, in order to check all result ing face systems, 2 (d+2)•(|V |-d) computations are required. We now examine each of these three cases separately, in order to exclude a very significant fraction of these computa tions.

First case (coordinate normals)

. Let F = (f i ) 1≤i≤m be the system of the sphere equa tions, let the initial forms be f e i for some normal e, and let F e be the resulting face system. We will deal with the coordinate normals case starting with an example.

Example 3

We present the equations of face system F e 1 in C 2 . Normal e 1 corresponds to variable x 1 . This means that the inner products with the exponent vectors of the monomials in the magnitude equation

f 1 = x 2 1 + y 2 1 -s 1 are 2, 0, 0. Thus, f e 1 1 = y 2 1 -s 1 , excluding the monomial x 2 1 .
In the case of the edge equation

f (1,2) = s 1 + s 2 -2(x 1 x 2 + y 1 y 2 ) + λ 2 1,2
, for a generic edge length λ 1,2 , the inner products are 0, 0, 1, 0, 0. It follows that f e 1 (1,2) = s 1 + s 2 -2y 1 y 2 + λ 2 1,2 . If the degree of x 1 in an equation f i is zero, then f e 1 i = f i , since the inner product of all the exponent vectors with e i is zero.

This example shows that since all x 1 monomials are removed, F e 1 is an overconstrained system that has the same number of equations as F , but a smaller number of variables. The same holds obviously for every F e i , while for e = i∈I e i (where I is an index set) the initial forms in F e are obtained after removing all monomials that include one or more of the variables corresponding to the e i 's of the sum. In other words, the initial forms in system F e can be obtained by evaluating to zero all the variables indexed by the set I.

Lemma 2 Let e be a sum of e i normals as described above. Now, F does not verify Bernstein's condition in the coordinate normals case (and has an inexact BKK bound) due to system F e having a toric root r ′ , only if F has a root r with zero coordinate for at least one of the variables in I, such that the projection of r to the coordinates j ∈ I equals r ′ .

We can now exclude the case of sums of coordinate normals from our examination, since it shall not generically occur, because the next lemma shows that r has no zero coordinate.

Lemma 3 The set of solutions of the sphere equations for a rigid graph generically lies in

(C * ) d•n .

Proof:

We indicate by S(G, λ, K d (ρ)) the set of complex embeddings for a rigid graph G up to an edge labeling λ and the embedding of d fixed vertices ρ = (ρ 1 , ρ 2 , . . . ρ d ). This set of embeddings is finite by definition. If there is a zero coordinate in the solution set, there exists a vector ρ ′ ∈ C d , such that no zero coordinates belong to the zero set S * (G, λ, K d (ρ + ρ ′ )), where ρ + ρ ′ = (ρ 1 + ρ ′ , ρ 2 + ρ ′ , . . . ρ d + ρ ′ ). Since we want to verify Bernstein's condition for a generic number of complex embeddings of G, we can always use the second set of embeddings. □

This lemma excludes a total of 2 (d+1)•(|V |-d) cases when verifying Bernstein's second the orem for a given algebraic system.

Second case (noncoordinate normals).

In the second case, the inner product of ex ponent vectors with δ u is minimized for all variables X u with maximum degree. Let us give again an example to explain this statement.

Example 4 It is an example in C 2 for face system F δ 1 . The inner products for the magni tude equation

f 1 = x 2 1 +y 2 1 -s 1 and the edge equation f (1,2) = s 1 +s 2 -2•(x 1 x 2 +y 1 y 2 )+λ 2 1,2 , λ 1,2 being a generic edge length, are -2, -2, -1 and -1, 0, -1, -1, 0 respectively. So, f δ 1 1 = x 2 1 + y 2 1 and f δ 1 (1,2) = s 1 -2 • (x 1 x 2 + y 1 y 2 ). If the degree of a polynomial f i in the set of variables X u is zero, then f δu i = f i .
The number of equations of F δu equals the number of variables. Following Bernstein's proof on the discriminant conditions, we introduce a new system by applying a suitable variable transformation from the initial variable vector x to a new variable vector t with same indexing. This transformation uses an m × m full rank matrix B such that every monomial x α is mapped to t B•α (see [START_REF] Bernstein | The number of roots of a system of equations[END_REF][START_REF] Cox | Polytopes, resultants, and equations[END_REF] for more details). Furthermore, | det B| = 1 so that the transformation preserves the mixed volume of F [START_REF] Cox | Polytopes, resultants, and equations[END_REF].

In our case, we construct matrix B with the following properties:

B • δ T u = e (d+1)•(u-1)+1 , B • e T (d+1)•(u-1)+j = e (d+1)•(u-1)+j , ∀j ∈ {2, . . . , d + 1}, det(B) = ±1.
The intuition behind these choices is given in Lemma 4 and its proof. This yields the following map from variables x to new variables t:

x u,1 → 1 t u,1 , x u,2 → t u,2 t u,1 , • • • , s u → t u,d+1 t u,1 . (3.6)
We will refer to the set of x u,1 's as the δvariables of F , since the image of their exponent vectors is the set of δ u 's, while the exponent vectors for the other variables remain same. This transformation maps system F (x) to a new system F (t) of Laurent polynomials in the new variables. In the case of C 2 , the sphere equations are mapped as follows:

f u = 1 t 2 u,1 + t 2 u,2 t 2 u,1 - t u,3 t u,1
, (magnitude equations)

f (u,v) = t u,3 t u,1 + t v,3 t v,1 -2 • 1 t u,1 t v,1 + t u,2 t v,2 t u,1 t v,1 + λ 2 u,v (edge equations) .
The degree α( f , t u,1 ) of a polynomial f with respect to the variable t u,1 will be either zero or negative. Let us now multiply every polynomial in F (t) with each one of the monomials

t -α( f ,t u,1 ) u,1
. These monomials are defined as the least common multiple of the denominators in the Laurent polynomials f , yielding the following system F (t):

f u = 1 + t 2 u,2 -t u,1 t u,3 , (magnitude equations) f (u,v) = t v,1 t u,3 + t u,1 t v,3 -2 • (1 + t u,2 t v,2 ) + λ 2 u,v • t u,1 t v,1 . (edge equations)
This transformation yields the necessary conditions to verify if the face systems of the noncoordinate normals have solutions in (C * ) m . We will refer to t u,1 's as the set of δ variables of F (t), while the rest should be the evariables. Note that the transformation gives a wellconstrained system, while zero evaluations of the δvariables shall result to an overconstrained system, that should have no solutions if the bound is exact.

Lemma 4 There exists a sum δ of different δ u normals, such that face system F δ has a solution in (C * ) m if the algebraic system F (t), which is defined above, has a zero solution for t u,1 for one or more vertices u.

Proof: Matrix B is constructed to change the variables x u,1 to variables t u,1 , for vertices u. From the definitions of F (t) and F (t), it follows that given a monomial t β in a polynomial f of F (t), the inner product β, B • δ T u is not minimized among other monomials in f if and only if the degree of t u,1 in the respective monomial of the transformed polynomial f is positive. Thus, the existence of toric solutions for the face system F δu is equivalent to existence of toric solutions for the zero evaluation F (t, t u,1 = 0).

So, if F (t, t u,1 = 0) has a solution in C m such that F (t, t u,1 = t v 1 ,1 = • • • = t v k ,1 = 0) has a solution in (C * ) m , then F δu+ δv 1 +•••+ δv k has a solution in (C * ) m . □
The computational gain in this case is that, without the lemma, one would have checked every different combination of the δ u 's, namely a total of 2 |V |-d checks. Now, it suffices to check only one zero evaluation for each of them, hence only |V | -d checks.

Third case (mixed normals). The third case, that includes the sums of vectors δ u and e i can be also treated with the transformation F (t) introduced above. Since the minimization of the inner product is invariant for d of the d + 1 variables per vertex, the nonexistence of zero solutions in F (t) implies that no F w has solutions in (C * ) m for all vectors w that are sums of vectors δ u with those vectors e i for which the equality B • e T i = e i holds. In order to proceed we need the following lemma. This shows that using d of the d + 1 e i 's of a vertex suffices to verify if a face system of a mixed normal has solutions in C m .

Lemma 5 Let us define a sum of normals

-δ u = d+1 j=1 e (d+1)•(u-1)+j ∈ R d+1 .
For every w ∈ R m , such that w is a sum ofδ u and other normals outside the set { δ u , e (d+1)•(u-1)+1 , . . . , e (d+1)•(u-1)+d+1 } (hence in a subspace complementary to that of δ u ), the face system F w cannot have a solution in (C * ) m .

Note thatδ u is the sum of d + 1 normals in complementary subspaces.

Proof: We will treat the case of dimension d = 2 for simplicity of notation; the proof generalizes to arbitrary d. Without loss of generality, we consider u = 1. Then w ∈ R 3 × R m-3 with w = (-δ 1 , v) and v ∈ R m-3 . The inner products ofδ 1 with the exponent vectors of the magnitude equation in R 2 for the first coordinate are 2, 2, 1, so f -δ 1 1 = -s. It is obvious that no w which is a sum ofδ 1 and normals not belonging to the set { δ 1 , e 1 , e 2 , e 3 } defines a face system with no solutions in (C * ) m . Similarly, the inner products ofδ 1 with the exponent vectors of the magnitude equation

f 1 = x 2 1 + y 2 1 + z 2 1 -1 on S 2 are 2, 2, 2, 0, yielding f -δ 1 1 = -1 which has no solutions in C m . □
Lemma 5 reveals that in order to verify the conditions of Bernstein's theorem, we can use the transformations F (t) for all choices of d variables from every set X u , since there is no need to check the cases that include the sum of all e i normals of a single vertex. This result, combined with Lemmas 3 & 4 leads to the following corollary.

Corollary 4 There is a vector w ∈ R m such that the face system of the sphere equations F w has a toric root if and only if there is a choice of δvariables such that the transformed algebraic system F (t) has a zero solution in C m for at least one δvariable.

Since the first d coordinate variables x u,j are symmetric (while s u variables are not), we can exploit these symmetries excluding some choices. So, without loss of generality, we may keep x 1,1 as a δvariable from variable set X 1 , and check all possible choices for δvariables from all other variable sets X u , such that u = 1 and u is not among the fixed vertices.

Summary of three cases.

In general, if one selects to take into consideration all pos sible sums of facet normals, then 2 (d+2)•(|V |-d) cases should be checked. We have shown that the category of face systems defined by a sum of coordinate normals cannot have toric solutions, discarding 2 (d+1)•(|V |-d) cases. In the two other cases, the investigation of toric solutions can be combined using the F (t) transformation. If a face system has toric solu tions, then in the noncoordinate normals case some δvariables may have zero solutions, while in the mixed normals case both δvariables and evariables may have zero solutions.

A naive approach to verify these two cases would result to 2 This discussion yields an effective algorithmic procedure (see Algorithm 2) to verify whether the mBézout bound is exact. Function ConstructDeltaPoly takes as input the system of the sphere equations F and a list of δvariables to construct the polynomials F (t). The central role is played by function IsmBezoutOfGraphExact, which verifies if the polynomials F have zero solutions for the δvariables.

Let us present two examples, further treated in the code found in [START_REF] Bartzos | Source code and examples for the paper[END_REF].

Example 5

The first (and the simplest nontrivial) example we have treated is an applica tion of our method to the equations that give the embeddings of Desargues graph (double prism) in C 2 and S 2 (see Figure 3.3). The embedding number for this graph in R 2 is 24 [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF] and on S 2 it is 32 (see Chapter 5). They both coincide with the generic number of complex solutions of the associated algebraic system. The mBézout bound for these systems is 32, hence it is inexact in the C 2 case. This shall be explained by the fact that the sphere equations in C 2 have face systems of noncoordinate normals with toric roots. The system of the sphere equations (with vertices 1 and 2 fixed) is a 12 × 12 well constrained system, but we can easily eliminate the linear equations obtaining an 8 by 8 wellconstrained system. Subsequently, we can also fix vertex 3 up to reflection about the edge (1, 2), obtaining finally a system of 6 polynomials in the variables {x 4 , y 4 , x 5 , y 5 , x 6 , y 6 }.

= u∈V ′ {x u,L(u) → 1 t u,L(u) }    u∈V ′ l∈{1,••• ,d+1}\{L(u)} {x u,l → t u,l t u,L(u) }    F (t) = F (changevars) F (t) = {} for f ∈ F (t) do /* α( f , t u,L(u) ) = (non-positive) degree of f in variable t u,L(u) */ f = u∈V ′ t -α( f ,t u,L(u) ) u,L(u) • f F (t) = F (t) { f } return ( F (t))
If we apply the transformation of variables mentioned above, we can construct a system of polynomials in variables {t 4,1 , t 4,2 , t 5,1 , t 5,2 , t 6,1 , t 6,2 }, such that evaluating t 4,1 , t 5,1 or t 6,1 to zero corresponds to the face systems of δ 4 , δ 5 or δ 6 respectively. This is one possible choice of δvariables to construct F (t). Solving these 3 different systems for every δ u with Gröbner basis in Maple we find the existence of solutions in C 2 , indicating that the number of complex solutions is strictly smaller than the mBézout bound.

In order to get nonzero solutions in C 2 , we need to evaluate to zero all t 4,1 , t 5,1 , t 6,1 variables, implying that the normal direction for which Bernstein's second theorem shows mixed vol ume to be inexact is ( -1, -1, -1, -1, -1, -1). This is a normal of a 3dimensional face, where the face dimension is obtained as 63. The normal equals the sum of 3 facet nor mals.

In the spherical case, no solutions exist, not only for the first choice of F (t), but also for all the other possible ones (see Algorithm 2), suggesting that the bound is tight, so the number of spherical embeddings is 32 and equals the mBézout bound.

Example 6

The JacksonOwen graph has the form of a cube with an additional edge adjacent to two antisymmetric vertices (see Figure 3.4). This graph is the smallest known case that has fewer real than complex embeddings, in R 2 and C 2 respectively [START_REF] Jackson | Equivalent realisations of a rigid graph[END_REF]. The mBézout bound up to the fixed edge shown in the figure is 192, while the number of embeddings in C 2 is 90. This shall be explained by a face system of mixed normals that has toric roots.

The system of the sphere equations is 18 × 18, reduced to 13 × 13 after linear elimination. The set of variables is {x 3 , y 3 , x 4 , y 4 , x 5 , y 5 , x 6 , y 6 , x 7 , y 7 , x 8 , y 8 , s 8 }. We found a solution following zero evaluation of all δvariables of F (t) and t 8,3 . The normal direction is 13 . This is an example for the mixed normals case, the normal being a sum of one e i and all 6 δ u 's.

(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0) ∈ R
Another way to apply our method is the computation of a suitable resultant matrix for a given overconstrained system, which follows from evaluating some variable to zero. It is obvious that if the system has any solutions, the rank of the resultant matrix with sufficiently generic entries is strictly smaller than its size, otherwise it has full rank, assuming we have a determinantal resultant matrix. We have used multires module for Maple [START_REF] Busé | Multires, a Maple package for multivariate resolution problems[END_REF] to examine the existence of solutions, repeating the previous results. However, these tools seem to be slower than other techniques which directly compute the embedding number.

In all our experimental computations, the existence of zero solutions of only one choice of F (t) (and not all d |V |-d-1 ) suffices to verify Bernstein's conditions. Therefore, we state the following conjecture: Conjecture 1 The conditions of Bernstein's second theorem for the system of the sphere equations F are satisfied if and only if the system F (t) has solutions for every zero eval uation of the δvariables.

If

UPPER BOUNDS ON THE EMBEDDING NUMBER OF MINIMALLY RIGID GRAPHS

In this Chapter we present methods that improve the upper bound of the embedding num ber for minimally rigid graphs. Unless specified alternatively, we consider the case of minimally rigid graphs in C d that have at least one complete subgraph K d for the com putation of the bounds. The asymptotic order of these bounds applies in the absence of such subgraph as well.

In Section 4.1 we use existing bounds that improve the upper bounds for d ≥ 5 and planar Geiringer graphs. Subsequently, in Section 4.2 we develop a method that bounds the number of outdegree constrained orientations and leads to better bounds in all dimen sions. We summarize the asymptotic upper bounds of this Chapter in Table 4.1, juxtapos ing the classic Bézout bound to the results of our methods.

The results of Section 4.1 have been published in [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF], while the results of Section 4.2 have been accepted for publication [START_REF] Bartzos | New upper bounds for the number of embed dings of minimally rigid graphs[END_REF].

Application of existing bounds on permanents and orientations

In this Section we make use of both methods presented in Chapter 3 for the mBézout computation. Applying directly bounds on (0, 1)-matrix permanents (the BrègmanMinc bound) and planar graph orientations, we improve upon the Bézout bound of the embed ding number for certain classes of minimally rigid graphs.

First, we make use of the following proposition on the asymptotic bounds for the orienta tions of planar graphs in order to improve the asymptotic upper bound of planar Geiringer graphs, which are the only fully characterized class of minimally rigid graphs in 3d space, and hence of special interest.

Proposition 1 (Felsner and Zickfeld [30])

The number of outdegree constrained orien tations of a planar graph is bounded from above by

2 |V |-4 • u∈I 2 -deg(u)+1 • deg(u) outdeg(u) (4.1)
where I is an independent set of the graph, deg(u) and outdeg(u) are respectively the degree and the outdegree of a vertex u. Furthermore, in the case of outdeg(u) = 3 this bound asymptoticaly behaves as 3.5565 |V | .

Given the relation between mBézout bounds and graph orientations (see Theorem 3), this proposition leads to the following improvement upon the asymptotic upper bound for the number of embeddings of the subclass of planar Geiringer graphs. Notice that planar Geiringer graphs are edge graphs of simplicial polyhedra [START_REF] Gluck | Almost all simply connected closed surfaces are rigid[END_REF], so there are always triangle subgraphs for them.

We also employ the permanent to obtain asymptotic improvement upon Bézout's asymp totic bound for d ≥ 5 by using the following bound.

Proposition 2 (Brègman [START_REF] Brègman | Some properties of nonnegative matrices and their permanents[END_REF], Minc [START_REF] Minc | Upper bounds for permanents of (0, 1)matrices[END_REF]) For a (0, 1)permanent A of dimension m, it holds:

per(A) ≤ m j=1 (ν j !) 1/ν j , (4.2)
where ν j is the sum of the entries in the jth column (or the jth row).

This leads to the following result.

| • d -d 2 , the Bézout bound is Be d (|V |) = 2 |V |•d-d 2 .
The sum of columns for the permanent that computes the mBézout bound is ν j = d for the edges that include one fixed vertex and one nonfixed vertex and ν j = 2d for these that include two nonfixed vertices. We denote these sets of edges E f. and E n.f. respectively. Applying the BrègmanMinc bound and Equation (3.5) we get

mBe d (|V |) ≤ 2 d! |V |-d • E f. i=1 (d!) 1/d E n.f. (2d!) 1/2d ≤ 2 • (2d)! d! |V |-d . ( 4
2 |V |•d-d 2 > 2 • (2d)! d! |V |-d ⇔ 2 2d-2 • (d!) 2 > (2d)!
Robbins' bound on Stirling's approximation [START_REF] Robbins | A remark on Stirling's formula[END_REF] yields the following:

√ 2π • d d+1/2 • e -d • e R -< d! < √ 2π • d d+1/2 • e -d • e R + ,
where

R + = 1 12d
and R -= 1 12d + 1

. We now derive the following inequalities:

2 2d-2 • (d!) 2 > 2 2d-2 • 2π • d 2d+1 • e -2d • e 2R - > √ 2π • 2 2d+1/2 • d 2d+1/2 • e -2d • e R + /2 > 2d!
that lead to a sufficient condition for Be d (|V |) > mBe d (|V |) to hold:

√ d > 4 √ π • e R + /2-2R -, (4.4)
which is true for every integer d ≥ 5.

Additionally, inequality (4.3) leads directly to the asymptotic bound

mBe d (|V |) ∈ O   2 • (2d)! d! |V |   (4.5)
for any given d. □

Obviously the asymptotic bound works also in the absence of K d , since in the worst case there will be d -2 additional non fixed edges, so the exponent in Inequality 4.3 would be |V | -2 and the asymptotic order would be the same (See Appendix B).

A new method to reduce the upper bounds of the embedding number

In this section we develop a method to improve the upper bound on the embedding num ber of minimally rigid graphs. We introduce a graph structure that inherits some of the properties of minimally rigid graphs, which we call pseudographs. Then, we apply an iter ative method that eliminates a vertex or a path in each step, while maintaining some basic properties of the pseudograph. This is used initially to bound the number of orientations for connected pseudographs with fixed outdegree equal to 2, since these orientations are related with the mBézout bound of sphere equations for Laman graphs improving the ex isting upper bounds. In the sequel, we generalize this method for minimally rigid graphs in bigger dimensions. Finally, we derive general asymptotic formulas for our method.

Pseudographs and orientations with fixed outdegree 2.

We define the following graphical structure generalizing that of a graph. Let the total degree p of a vertex v denote the total number of (normal and hanging) edges incident to v. Let h denote the hanging degree of v, which is the number of hanging edges incident to v, while the number of normal edges incident to v is its normal degree and equals p -h. The extended degree of v is the pair (p, h). We shall consider orientations of a pseudograph L defined by specifying a direction on every normal edge, while by definition hanging edges are directed out of their unique vertex. Pseudograph orientations refer to the orientations of pseudographs. We count pseudograph orientations with fixed outdegree 2 for all vertices: we call these orientations valid. Clearly, if a vertex has a hanging edge, one more edge should be directed out of it, while if it has hanging degree 2, all its normal edges should be indirected. A pseudograph containing a vertex with extended degree (p, h), such that p < 2 or h > 2, has no valid orientations.

Definition 3 A pseudograph L(V, E, H) is a collection,
We now prove the following necessary condition for the existence of a valid orientation of a pseudograph (which resembles Maxwell's count).

Iterative elimination

Now we present the basic graphical operations used to reduce the size of a connected pseudograph. We specify an iterative elimination process comprised of a sequence of steps, with the requirement that the pseudograph stays connected. We shall distinguish two types of steps, depending on the extended degree of the vertex, or of the vertex path to be eliminated. The process terminates when the current pseudograph's normal subgraph is a tree; see details in Proposition 6.

(a) (b) Let us detail the two types of elimination steps.

The first type eliminates a single vertex v with extended degree other than [START_REF] Bartzos | On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs[END_REF][START_REF] Asimow | The rigidity of graphs[END_REF]. Let L(U, F, H) be a pseudograph: We choose to eliminate two edges incident to v (Fig ure 4.2a), thus maintaining the total edge count of Proposition 3. If v is incident to h ≤ 2 hanging edges, these must be eliminated. Since the outdegree of v equals 2 in a valid orientation of L, there are 2 -h ≤ 2 normal edges incident to v that get eliminated. All edges that are not eliminated become hanging in the new pseudograph, and correspond to edges directed towards v for a valid orientation of the initial pseudograph. The second type eliminates a path of ℓ ≥ 2 consecutive vertices, all of extended degree (3, 1) (Figure 4.3); we avoid single (3, 1) vertex elimination because that would yield a looser bound. Edges are eliminated similarly as before, namely we eliminate the ℓ hang ing edges (one per vertex) and another ℓ normal edges incident to path vertices, thus eliminating 2ℓ edges. After eliminating the path, there are two choices for the normal edge that remains; in either case, it becomes hanging (Figure 4.2). Now, we introduce two parameters for controlling the elimination process, namely the cost and the hanging edge equilibrium.

In every elimination step, there are several ways to choose the edges that remain in the new pseudograph. The number of choices corresponds to different pseudographs with valid orientations; their number is defined to be the cost of the step.

Remark 1

The product of the costs of all steps in the elimination process bounds the number of valid orientations of the initial pseudograph. In other words, the cost expresses the quotient of the valid orientations of the original graph over the maximum number of valid orientations of the resulting graphs.

In the proposition that follows, we show that, for vertex elimination, the cost is determined by the extended degree of the eliminated vertex, while for path elimination, the cost always equals 2.

Another important quantity in the elimination is the hanging edge equilibrium, defined as the difference between hanging edges in the resulting pseudograph and the original one.

Proposition 4 Let v be a vertex with extended degree (p, h), then the cost and the hanging edge equilibrium of the elimination step are given by p -h 2 -h , and p -h -2 respectively. In the case of path elimination, for a path of length ℓ, the cost is 2 and the hanging edge equilibrium is 1 -ℓ.

Proof: Recall that at vertex elimination, two edges are eliminated and, when there are hanging edges, these are eliminated first. So 2 -h edges are left to be eliminated among the p -h normal edges of the vertex, which yields the cost of this step. Since 2 -h edges were eliminated, the number of the new hanging edges is p -h -(2 -h), while the initial number of hanging edges was h. Their difference yields p -h -2.

Let us view path elimination as a sequence of vertex eliminations. Then, eliminating the first vertex has cost 2. Each following vertex now has degree (2, 1) or (3, 2), hence its elimination cost is 1. Therefore the overall cost is 2 because it equals the product of all costs. As for the hanging edge equilibrium, the path contains ℓ hanging edges and, after the elimination step, one remains. □

If the iterative process continued up to the exhaustion of vertices and, moreover, all cases were as in Figure 4.2(a), there would be O(3 |V | ) orientations which, by Theorem 3, yields a bound of O( 6|V | ) on Laman embeddings. However, our process is defined to terminate earlier; see Proposition 6.

Bounding the number of valid orientations

In this subsection, by applying the process described above, we bound the number of valid orientations of connected pseudographs. In the sequel, n denotes the number of vertices of a connected pseudograph and k the total number of its hanging edges.

We first prove that there is always an elimination process that keeps the pseudograph connected. For this, we recall the definition of a blockcut tree [START_REF] Harary | Graph Theory[END_REF]Chapter 4]. Recall that a cutvertex is such that its removal increases the number of connected components in the graph and a biconnected component is a maximal subgraph with no cut vertices 2 .

Definition 4 (Harary [START_REF] Harary | Graph Theory[END_REF]) Let G(V, E) be any graph. Let also bc(G) be the graph such that:

• This graph has a vertex for each biconnected component, and for each cutvertex of G.

• There is an edge in bc(G) for each pair of a biconnected component in G and a cutvertex that belongs to that block.

If G is connected, then bc(G) is a tree and is called blockcut tree of G.

Following Definitions 3 and 4, blockcut trees can be used in the case of normal subgraph G(V, E) of a connected pseudograph L(V, E, H) (Figure 4.4).

We can now prove the following statement, which allows us to use the bound in Expres sion (4.7). E,H) and the blockcut tree of its normal subgraph G(V, E).

B 1 v c l u,c u c B 2 B 3 B 1 v c l u,c u c B 2 B 3 L(V, E, H) bc(G) Figure 4.4: A pseudograph L(V,
Proposition 5 Given a connected pseudograph L(V, E, H), there is always an elimination process where, in each step, we either eliminate a vertex with extended degree other than (3, 1), or we eliminate a (3, 1)path with length at least 2, so that the resulting pseudograph remains connected.

Proof: If there is a noncut vertex with degree other than (3, 1), then it can be eliminated and the proposition holds.

We now show that, if all vertices in L with degree other than (3, 1) are cutvertices, then there are at least two adjacent (3, 1)vertices that can be eliminated keeping the pseudo graph connected (an example is shown in Figure 4.4). Since L is connected, its normal subgraph G is connected as well, and there exist noncut vertices in G; their extended degree must equal [START_REF] Bartzos | On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs[END_REF][START_REF] Asimow | The rigidity of graphs[END_REF].

From the definition of blockcut trees, the leaves of bc(G) represent biconnected compo nents in G. In these components, all vertices but one are noncut vertices, and their normal degree is 2, since their extended degree is (3, 1). If such biconnected component had only one noncut vertex, then this vertex would have normal degree 1. This means that there are at least two such vertices in a biconnected component of L and, since their normal de gree equals 2, there exists a path containing ℓ ≥ 2 such vertices, denoted (v 1 , . . . , v ℓ ). This path can be eliminated and the resulting pseudograph remains connected; more precisely, we may eliminate successively each v i , thus making vertex v i+1 have normal degree 1.

This completes the proof. □

Concerning the termination condition of our process, we establish the following for a con nected pseudograph whose normal subgraph is a tree. Proof: Since G(V, E) is a tree, we can always eliminate a vertex of normal degree 1 from our pseudograph. This means that p -h = 1, so using the formulas of Proposition 4 it is obvious that, if there is a valid orientation, then this is unique. If it does have a valid orientation, then from the total edge count in Proposition 3, we deduce

|E| + k = 2 • n.
Since G is a tree, we substitute |E| = n -1 in this formula, concluding the proof. □

Let P (n, k) denote the maximal number of valid orientations for all connected pseudo graphs with n vertices and k hanging edges. Let us recall the BrègmanMinc bound and the connection between permanents, constrained orientations, and the bound of Laman graphs as discussed in Chapter 3 and in [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs[END_REF], where it was established that:

P (n, k) ≤ (2!) k/2 (4!) (2n-k)/4 • (2) -n ≈ 2.4495 n • 0.6389 k . ( 4.6)
We therefore seek upper bound estimates of the form

P (n, k) ≤ ζ n ε k (4.7)
for real ζ, ε > 0 and k, n ≥ 1.

Proposition 6 implies P (n, n + 1) = 1 for every n ≥ 1; this is the base case in Theorem 9. Proposition 5 precludes that multiple connected components be formed, thus leading to the theorem's inductive proof. Additionally, Propositions 3 and 6 establish that k ≤ n + 1 for any connected pseudograph with at least one valid orientation. Indeed, k > n + 1 implies the normal subgraph has < n -1 edges so cannot be connected.

We modify the form of the bound in Inequality (4.7

) to P (n, k) ≤ ζ n ε k-1 , with ζ, ε > 1.
The modification is justified in the proof below.

Theorem 9

The number of valid orientations for a connected pseudograph is bounded above by

P (n, k) ≤ ζ n • ε k-1 ,
where ζ = 24 1/5 and ε = 18 -1/5 .

Proof:

We prove the statement by induction on n, k. The statement is true for the base cases n = 1, k = 2, which a pseudograph consisting of exactly one (2, 2) vertex, and also for trees with k = n + 1, since P (n, n + 1) = 1 (Proposition 6), because ζε > 1. In these cases the pseudograph has 1 or 0 orientations, representing a termination condition. If the exponent of ε were k, the statement would fail for small trees.

From Propositions 3 and 6, if a connected pseudograph has k > n hanging edges, either it is a tree, or it has no valid orientations. So we assume pseudograph L, with n > 1 vertices, has k ≤ n hanging edges. Suppose it has a vertex v of extended degree (p, h), such that:

1. (p, h) = (3, 1), and 2. elimination of v and its incident edges keeps the pseudograph connected.

Since the number of valid orientations of L is bounded by the cost of the elimination pro cess (Remark 1) and the hanging edge equilibrium is p -h -2, the number of valid orien tations after eliminating this vertex is bounded by

p -h 2 -h P (n -1, k + p -h -2).
By the induction assumption, this is bounded by

C(p, h) ζ n ε k-1 , where C(p, h) = p -h 2 -h ζ -1 ε p-h-2 .
We now prove that C(p, h) ≤ 1, for p ≥ 2 ≥ h ≥ 0, and (p, h) = (3, 1). Direct substitution gives

C(p, h) = p -h 2 -h 2 h-p-1 3 2h-2p+3 1/5 .
Note that:

• C(2, 0) = 24 -1/5 < 1, C(3, 0) = (9/16) 1/5 < 1, C(4, 0) = 1, and the C(p, 0) for p > 4 are decreasing with p as follows:

C(p + 1, 0) C(p, 0) = 1 + 2 p -1 ε < 1, for p ≥ 4. (4.8)
• C(2, 1) = (3/4) 1/5 < 1, C(4, 1) = (9/16) 1/5 < 1, and the C(p, 1) for p > 4 are decreas ing with p as follows:

C(p + 1, 1) C(p, 1) = 1 + 1 p -1 ε < 1, for p ≥ 4. (4.9)
• C(3, 2) = (3/4) 1/5 < 1, and the C(p, 2) for p > 3 are strictly decreasing with p, as the binomial factor equals the constant 1.

C(2, 2) is immaterial since (2, 2
) is a base case corresponding to a pseudograph with a single vertex and k > n.

An induction step is proven under the assumptions (i)-(ii). Incidentally, C(3, 1) = (4/3) 1/5 > 1, which is why we avoid eliminating this type of vertices in a vertex elimination step.

If assumptions (i)-(ii) fail, we can eliminate a path of (3, 1)vertices keeping the pseudo graph connected by Proposition 5.

Let ℓ ≥ 2 denote the number of vertices in the eliminated path. Then, the number of orientations of L is bounded by

2P (n -ℓ, k -ℓ + 1),
which, by induction, is bounded by

2 ζ n-ℓ ε k-ℓ = 3 4 (ℓ-2)/5 ζ n ε k-1 ≤ ζ n ε k-1 .
The bound is proven. □

A new upper bound on the embedding number of Laman graphs

This subsection combines the above discussion so as to establish a new upper bound on the number of embeddings for Laman graphs.

Let G(V, E) be a Laman graph and a fixed edge e = (v

1 , v 2 ) ∈ E. Let also L G,e (V ′ , E ′ , H) be a collection such that V ′ = V \{v 1 , v 2 }, E ′ = {e ′ ∈ E : v 1 , v 2 / ∈ e ′ }
and H is the set of all edges incident to one fixed vertex and one non fixedvertex. Then L G,e is a pseudograph that may contain one or multiple connected components; in A different choice of a fixed edge may result in different pseudographs, for a given Laman graph, while different Laman graphs may result in the same pseudograph, see Figure 4.6. This happens because any pseudograph representation lacks the information on connec tions with specific vertices of the fixed edge.

From the construction of L G,e it follows that, when it is connected, its number of valid orientations equals that of its constrained orientations defined in Theorem 3. This bound is always positive, since it corresponds to wellconstrained algebraic systems. If L G,e has µ > 1 connected components L 1 , . . . , L µ , then the total number of valid orientations of L G,e equals the product of valid orientations per connected component L i . This leads to the following corollary, which distinguishes components with one vertex in order to exploit Maxwell's count.

Corollary 5

Let G(V, E) be a Laman graph and L G,e constructed as described above. Let µ ′ be the number of connected components of L G,e with more than one vertex, and n the number of its vertices. Then, the number of constrained orientations, defined in Theorem 3, is bounded above by

24 n/5 • 18 -(k ′ -µ ′ )/5 ,
where k ′ is the total number of hanging edges in the components of L G,e with more than one vertex. Proof:

Proof: Recall that n = |V | -2. Let n 1 , n 2 . . . n µ ′ and k 1 , k 2 . . . k µ ′ be
Let L i (V i , E i , H i ) be a connected component of L G,e with k i hanging edges. The normal subgraph G i (V i , E i ) is a subgraph of a Laman graph. If |V i | ≥ 2, by Maxwell's count we have |E i | ≤ 2 • |V i | -3 therefore k i ≥ 3. □
Now we are ready to prove the new upper bound for Laman graphs.

Theorem 10 Let G(V, E) be a Laman graph. Then the number of its embeddings in C 2 (and S 2 ) is bounded from above by

18 -2/5 • 4 • (3/4) 1/5 |V |-2 = O 3.7764 |V | .
Proof: Applying k ′ ≥ 3µ ′ from Lemma 6 in Corollary 5, the number of valid orientations is bounded by 24 n/5 • 18 -2/5 , for n ≥ 2, since either the number of connected components with more than one orientation is µ ′ ≥ 1, or there is a single valid orientation. By doubling this bound and applying Theorem 3, the upper bound follows. For n = 1, Lemma 6 does not apply; there is trivially one orientation and the bound is 2. □

Geiringer graphs and higher dimensions

This subsection extends the method of the previous section to orientations of connected pseudographs with fixed outdegree d ≥ 3, and subsequently establishes new upper bounds on the embedding number of minimally rigid graphs in C d (and S d ), for d ≥ 3.

Let P d (n, k) denote the maximal number of orientations with fixed outdegree d for con nected pseudographs with n vertices and k hanging edges. As before, we seek bounds of the form

P d (n, k) ≤ ζ n d • ε k-1 d
for each d. For a fixed outdegree d ≥ 3, the elimination steps consist of:

• Eliminating single vertices of extended degree (p, h), with p ≥ d ≥ h ≥ 0, and

(p, h) = (d + 1, d -1); then the number of valid orientations is bounded by p -h d -h • P d (n -1, k + p -h -d).
• Eliminating paths of length ℓ ≥ 2 with (d + 1, d -1)vertices; then the number of valid orientations is bounded by An immediate consequence is that, if a connected pseudograph has a tree as normal subgraph and also has an orientation with fixed outdegree d, then it holds that (d -1) • n = k -1 which is our base case, generalizing Proposition 6. In the following theorem we establish an upper bound on P d . If d = 2, then ζ 2 , ε 2 are evaluated as in Theorem 9. Here, elimination of single vertices of extended degree (d, d) and (d + 1, d -1) are excluded from our analysis. The first case because it is one of the base cases, as a pseudograph with exactly one vertex, and the latter because only path elimination with length ℓ ≥ 2 is considered for these vertices.

2 • P d (n -ℓ, k -(d -1)ℓ + 1).

Theorem 11

The maximal number of orientations with fixed outdegree d for a connected pseudograph is bounded from above by

P d (n, k) ≤ ζ n d • ε k-1 d
for the following choices of ζ d and ε d :

ζ d = max p≥d 2 p-d p d 2d-3 1 2p -3 , ( 4.10)
and

ε d = 2 p d -2 1 2p -3 (4.11)
for the value of p that maximizes ζ d .

Proof: The single vertex elimination step and the path elimination step result in the fol lowing inequalities: Our key observation is that (4.12) for a relevant pair (p, h) is satisfied if:

ζ d ε d+h-p d ≥ p -h d -h (4.12) for all (p, h) ∈ {(d + 1, d -1), (d, d)} with p ≥ d ≥ h,
1. The same inequality is satisfied for the shifted

p → p + 1, h → h -1, giving ζ d ε d+h-p-2 d ≥ p -h + 2 d -h + 2 .
2. Inequality (4.13) is satisfied for ℓ = 2.

This implies that it is enough to consider (4.12) with h = 0. Considering (ii) with ℓ = 2 and a particular case of (4.12) with h = 0, the two inequalities can be raised to nonnegative powers and combined so as to eliminate ε d , with the conclusion that

ζ 2p-3 d ≥ 2 p-d p d 2d-3
.

A permissible equality is achieved together with Equality (4.11). The maximization in Equality (4.10) through p ≥ d follows.

It remains to prove the key observation. Inequalities (i)-(ii) can be raised to positive powers and combined, with the conclusion that

ζ d ε d+h-p d ≥ p -h + 2 d -h + 1 2p-2h-3 2p-2h+1
U (χ, ψ) = 1 4 χ ψ 4 (χ -ψ + 1)(ψ + 1) (χ + 1)(χ + 2) 2χ-3
.

The inequality has to be shown for integer χ ≥ ψ ≥ 0 such that (χ, ψ) / ∈ {(2, 1), (0, 0), (1, 0), (1, 1)}, which correspond respectively to vertices ( d+1,(d,d),(d+ 1,d),(d,). For fixed ψ, the maximum is achieved at χ = 2ψ, since U (χ, ψ) increases. This follows from

U (χ + 1, ψ) U (χ, ψ) = (ψ + 1) 2 (χ -ψ + 1)(χ -ψ + 2) 1 - 1 (χ + 2) 2 1 - χ -2ψ + 1 (χ + 3)(χ -ψ + 1) 2χ .
This ratio is < 1 for χ ≥ 2ψ, and (by calculus on the product of the first and middle terms) it is > 1 for χ < 2ψ.

For this pair of values, we have

U (2ψ, ψ) = 2 ψ κ=1 1 - 1 κ (2κ + 1) 4κ-3 .
Evidently, the χmaximum U (2ψ, ψ) is a decreasing function of ψ, and U (4, 2) = 3 9 /25000 < 1. For ψ < 2, we observe that U (χ, 1) ≤ U (3, 1) = 3 7 /4000 < 1 and U (χ, 0) < U (1, 0) = 3/4 < 1 for χ > 2.

□

We now describe a construction similar to Section 4.2.4, connecting Theorem 3 to the orientations of pseudographs with fixed outdegree d and n > 1. Let G(V, E) be a minimally rigid graph in C d and let K d be one of its subgraphs. Removing K d , as in the case of d = 2, we have a pseudograph, denoted

L G,K d (V ′ , E ′ , H).
Applying Maxwell's condition to the edge count for the normal subgraphs of the pseu dographs, we obtain k i ≥ d+1

edges and ≥ d -2 hanging edges, so k i ≥ 3d -3. By induction, for the ith vertex, at least i -1 hanging edges shall be added.

Hence, if L G,K d has µ ′ connected components with more than 2 vertices and a total of k ′ hanging edges, then k ′ ≥ 3d -3 for d ≥ 3.

An immediate consequence is the following theorem that generalizes Theorem 10 by ap plying Theorem 3.

Theorem 12

Let G(V, E) be a minimally rigid graph in C d (and S d ) that contains a K d .

Then the number of its embeddings is bounded from above by

ε 3d-2 d • (2 • ζ d ) |V |-d = O((2 • ζ d ) |V | ).
In the case of Geiringer graphs that contain a triangle this is

2 • 10 2 -5/9 8 • (5/8) 1/3 |V |-3 = O 6.8399 |V | .
The asymptotic bound works also for minimally rigid graphs in C d that do not contain a K d . In that case, we may remove a maximal clique with d ′ ≥ 2 vertices in order to obtain a pseudograph. Then, the exponent of ζ d will never exceed |V | -2 (see Appendix B for details).

To demonstrate the improvement achieved by our this new bound on the embedding num ber of rigid graphs, namely O (2ζ d ) |V | , we refer the reader to Table 4.1 which compares the values of 2ζ d to the power basis of Bézout bound and the bound derived in Section 4.1.

ON THE MAXIMAL NUMBER OF REAL EMBEDDINGS

IN R 2 , R 3 AND S 2
In this chapter we deal with the problem of finding edge length parameters that maximize the real embeddings of Laman and Geiringer graphs. We use both algebraic formulations presented in Section 2.2 and we use the complex embedding number as an upper bound.

In Section 5.1 we present the sampling methods we use in order to increase the number of real embeddings. Besides standard sampling methods, an algorithm inspired by coupler curves has been developed by J.Legerský in order to search efficiently huge parametric spaces combining local and global sampling in the case of Geiringer graphs.

The main results of our methods are presented in Section 5.2. These include a full char acterization of graphs with a small number of vertices up to their real embedding number. More precisely we give the maximal numbers of real embeddings of all 6vertex and 7 vertex Laman graphs in S 2 and R 2 respectively, as well as the maximal numbers of real embeddings of all 7vertex Geiringer graphs. We also specify parameters for selected bigger graphs. These computations improve the existing lower bound on the maximal number of real embeddings from 2.3003 The part of this Chapter related to Geiringer graphs appear in the conference proceedings of ISSAC'18 [START_REF] Bartzos | On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs[END_REF]. The totality of the results have been published in [START_REF] Bartzos | On the maximal number of real embeddings of minimally rigid graphs in R 2 , R 3 and S 2[END_REF].

Increasing the number of real embeddings

Our main goal throughout our experiments was to find the parameters that can maximize the number of real embeddings of minimally rigid graphs. One open problem in rigidity theory is whether the maximal number of real embeddings of a given graph can be the same as the number of complex embeddings. Although there exists an 8vertex Laman graph for which it has been proven that r 2 (G) < c 2 (G) [START_REF] Jackson | Equivalent realisations of a rigid graph[END_REF], in most cases we consider the number of complex embeddings as the upper bound we try to reach (see also Chapter 1).

In our research, we concentrate on the cases of graphs with the biggest number of com plex embeddings, among all other minimally rigid graphs with the same number of vertices.

Additionally to some standard sampling methods, we develop a new method that can in crease efficiently the number of real embeddings for certain Geiringer graphs. Our method is inspired by coupler curves approach and uses G 48 (the 7vertex Geiringer graph with the maximal number of embeddings) as a model. Taking advantage of our implementation based on this technique, we increase lower bounds on r 3 (G) for many graphs and estab lish new asymptotic lower bounds on the maximal number of embeddings of Geiringer graphs.

Standard sampling methods

Finding initial configurations We applied different heuristics to find initial configura tions for our parameter sampling. First of all, we tried to compute the number of real embeddings of totally random configurations. This resulted in finding maximal numbers of real embeddings for graphs with c d (G) = 2 |V |-d . For example, it took less than 20 minutes to detect parameters that attain the maximum for all 8vertex nontrivial 1 Geiringer graphs with r 3 (G) = 32.

We also used almost degenerate locus as starting points. In order to increase r 2 (G) of Laman graphs with maximal numbers of complex embeddings w.r.t. a given number of vertices, we chose lengths very close to the unit length. Similarly, in the case of Geiringer graphs, we perturbed degenerate conformations. For example, in order to find an initial point for G 48 , we separated the edges into three sets with edge lengths being the same in each of them: the ring edges of the 5cycle, the top edges that connect v 7 with the ring and the bottom edges that connect v 1 with the ring (see Fig ure 5.1). We subsequently found edge lengths that maximized the intervals imposed by triangular and tetrangular inequalities up to scaling and we perturbed the resulting lengths.

Finally, we also used as starting points conformations of smaller graphs with maximal numbers of embeddings. For instance, gluing v 7 and v 8 in G 160 results in G 48 . Perturbing a set of edge lengths λ of G 48 such that r 3 (G 48 , λ) = 48, we could get a starting point for the sampling of G 160 that would result in a big number of real embeddings.

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8

Stochastic methods

We have used stochastic methods for different graphs in order to increase the number of embeddings. Our method uses a variant of the tools suggested in [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF]. We penalize the loss of real roots and the increase of the imaginary part of complex solutions to decide if the resulted labeling constitutes a new starting point. This method could increase the number of embeddings, but rarely attained the maximum.

Parametric searching with CAD method The methods described in the previous para graph are local methods. In order to search globally one parameter, we used Maple's subpackage RootFinding [Parametric] in Maple18. This package is an implementation of Cylindrical Algebraic Decomposition principles for semialgebraic sets. The input consists of the equations and the inequalities of the system and the list of variables separating them from parameters. The output is a cell decomposition of the space of parameters according to the number of solutions of the semialgebraic conditions.

In our problem, we were able to take advantage of this implementation using Cayley Menger determinants of 7vertex graphs and searching for only one parameter (See Sec tion 2.2.2). Sphere equations failed to give any result, while computational constraints did not let us search two or more parameters simultaneously.

This sampling was also used to increase the number of spherical and planar embeddings of Laman graphs with 7 vertices and the number of real embeddings of G 48 . In some situations it was even possible to attend the maximal number of embeddings for a given graph.

Coupler curve

The previous methods fail to attain tight bounds for Geiringer graphs with maximal number of embeddings efficiently. For example, using CAD, we could find 28 real embeddings for G 48 , but it seems impossible to increase this number by local searching in all parameters or global sampling only one of them. Thus, we developed a new method that samples only subset of edge lengths in every iteration. This procedure is motivated by visualization of coupler curves.

Let G(V, E) be a minimally rigid graph with a triangle and an edge (u, u ′ ).

If G ′ = (V, E \ (u, u ′ )
) is obtained from G by removing the edge (u, u ′ ), then the set of embed dings satisfying the constraints given by generic edge lengths and fixing the triangle is 1dimensional. The projection of this curve to the coordinates of the vertex u ′ is a so called coupler curve. The authors in [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF] used this idea for proving that the Desargues (3 prism) graph has 24 real embeddings in R 2 . Namely, they found edge lengths such there are 24 intersections of the coupler curve with a circle representing the removed edge. This approach can be clearly extended into R 3 -the number of embeddings of G is the same as the number of intersection of the coupler curve of u ′ with the sphere centered at u with a radius λ u,u ′ . Now, we define specifically a coupler curve in R 3 .

Definition 5 Let G ′ be a graph with edge lengths λ = (λ e ) e∈E G ′ with a triangle subgraph K 3 with vertexset {v 1 , v 2 , v 3 } and a specific embedding K 3 (ρ) satisfying edge length con straints. If the set S R (G ′ , λ, K 3 (ρ)) is one dimensional and u ′ ∈ V G ′ , then the set

C u ′ ,λ = {(x u ′ , y u ′ , z u ′ ) : ((x v , y v , z v )) v∈V G * ∈ S R (G ′ , λ, K 3 (ρ))}
is called a coupler curve of u ′ w.r.t. the fixed triangle K 3 (ρ).

Assuming that a coupler curve is fixed, i.e., we have fixed lengths λ of the graph G ′ , we can change the edge length λ u,u ′ so that the number of intersections of the coupler curve C u ′ ,λ with the sphere with the center at u and radius λ u,u ′ , namely, the number of real embeddings of G, is maximal.

The following lemma shows that we can change three more edge lengths within one pa rameter family without changing the coupler curve. This one parameter family corresponds to shifting the center of the sphere along a line.

Lemma 7

Let G(V, E) be a minimally rigid graph and u, v, w, q, u ′ be vertices of G such that (q, v), (v, w) ∈ E and the neighbours of u in G are v, w, q and u ′ . Let G ′ be the graph given by (V ′ , E ′ ) = (V, E \ {(u, u ′ )}) with generic edge lengths λ = (λ e ) e∈E ′ . Let C u ′ ,λ be the coupler curve of u ′ w.r.t. the fixed triangle with vertices {v, u, w} and an embedding ρ v,u,w . Let z q be the altitude of q in the fixed triangle with lengths given by λ. Then the set {y q : ((

x v ′ , y v ′ , z v ′ )) v ′ ∈V ′ ∈ S R (G ′ , λ, ρ v,u,w
)} has only one element y ′ p . If the parametric edge lengths λ ′ (t) are given by Proof: All coupler curves in the proof are w.r.t. the triangle defined above. Fig ure 5.2 illustrates the statement. Since G is minimally rigid, the set S R (G ′ , λ, ρ v,u,w ) is 1dimensional. The coupler curve C q,λ of q is a circle whose axis of symmetry is the yaxis. Hence, the set {y p : ((

λ ′ u,w (t) = ||(x w , y w -t, 0)|| , λ ′ u,q (t) = ||(0, y ′ q -t, z q )|| , λ ′ u,v (t) = t ,
x v ′ , y v ′ , z v ′ )) v ′ ∈V ′ ∈ S R (G ′ , λ, ρ v,u,w )} has indeed only one element.
The parametrized edge lengths λ ′ (t) are such that the position of v and w is the same for all t. Moreover, the coupler curve C q,λ ′ (t) of q is independent of t. Hence, the coupler curve C u ′ ,λ ′ (t) is independent of t, because the only vertices adjacent to u in G ′ are q, v and w. Thus, the positions of the other vertices are not affected by the position of u. □ Therefore, for every subgraph of G induced by vertices u, v, w, q, u ′ such that deg(u) = 4 and (q, v), (v, w), (u, v), (u, w), (u, q), (u, u ′ ) ∈ E, we have a 2parametric family of lengths λ(t, t ′ ) such that the coupler curve C u ′ ,λ(t,t ′ ) w.r.t. the fixed triangle vuw is independent of t and t ′ . Recall that the parameter t ′ represents the length of (u, u ′ ), which corresponds to the radius of the sphere, and the parameter t determines the lengths of (u, v), (u, w) and (u, p). Now, we aim to find t ′ and t such that r 3 (G, λ(t, t ′ )) is maximized.

Let us clarify that whereas [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF] were also changing the coupler curve, our approach is different in the sense that the coupler curve is preserved within one step of our method, while only the position and radius of the sphere corresponding to the removed edge are changed in order to have as many intersections as possible. In the next step, we pick a different edge to be removed.

x y z C q,λ x w y w C u ′ ,λ v u u(t) w q y ′ q u ′ z q Figure 5.2:
Since the lengths of λ u,q and λ u,w are changed accordingly to the length of (u, v) (blued dashed edges), the coupler curves C q,λ ′ (t) and C u ′ ,λ ′ (t) are independent of t. The red dashed edge (u, u ′ ) is removed from G.

In order to illustrate the method, let λ be edge lengths of G 48 given by Instead of finding suitable parameters for the position and radius of the sphere by looking at visualizations, we implemented a sampling procedure that tries to maximize the number of intersections [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF]. The inputs of the function sampleToGetMoreEmbd are starting edge lengths λ and vertices u, v, w, q, u ′ satisfying the assumptions of Lemma 7, including the extra requirement that (u ′ , w) is an edge. In order to count the real embedding number, we use the homotopy continuation package phcpy [START_REF] Verschelde | Modernizing PHCpack through phcpy[END_REF] for solving the algebraic systems.

λ 1,2 = 1.

Classification and Lower Bounds

A first upper bound on the number of embeddings is the mixed volume of systems of sphere and CayleyMenger varieties. This bound is crucial for homotopy continuation system solving, as mentioned before. Let us remark that, in the case of sphere equations the mixed volume is also equal to the mBézout bound almost always (see Section 3.2.1). On the other hand, in the case of CayleyMenger varieties these two bounds do not always coincide. The second natural bound of graph realizations is the number of complex embeddings. The numbers of complex embeddings for all Laman graphs up to 12 vertices are known from [START_REF] Capco | The number of realizations of a Laman graph[END_REF], while the numbers of complex embeddings of Geiringer graphs up to 10 vertices were computed by [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. We computed the complex solutions of spherical embeddings of Laman graphs up to 8 vertices. For the last part, we were motivated by a remark of Josef Schicho, who had observed that the numbers of planar and spherical solutions differ for the Desargues graph.

In order to find parameters that can maximize the number of real embeddings, we applied the methods described in Section 5.1. Polynomial system solving during sampling was accomplished mainly via phcpy. We consider an embedding being real if the absolute value of the imaginary part of every coordinate is less than 10 -15 . The final results were verified using Maple's RootFinding [Isolate]. Our results ameliorate significantly what was known about the bounds of real embeddings.

Embeddings of Laman Graphs on the plane

The numbers of realizations of all 6vertex Laman graphs are known [START_REF] Borcea | The number of embeddings of minimally rigid graphs[END_REF]. There are four nontrivial Laman graphs (requiring an H2 move in the last step of their construction see Section 2.1) and the upper bound of real embeddings was computed in [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF] for the graph with the maximal number of complex embeddings. Using stochastic and parametric methods, we were also able to maximize the number of embeddings for the other three 7vertex graph with not trivial number of embeddings, completing a full classification for all 7vertex Laman graphs according to their number of real embeddings [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF]. For bigger graphs, we focused on the graphs with the maximal number of complex em beddings, see Figure 5

L 136 L 344 L 880

Spherical embeddings of Laman graphs

Maximal numbers of embeddings in S 2 have been not studied so far. We attempted to find edge lengths such that the number of realizations was the same as the number of complex solutions for graphs that do not have a trivial number of embeddings. We shall observe again that the c 2 (G) varies for certain graphs from c S 2 (G).

We have found parameters such that all the embeddings are real for all nontrivial graphs with 6 and the 7vertex graphs with the maximal number of complex embeddings(they can be found in [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF]). The Desargues graph has the maximal number of embeddings among 6vertex graphs, namely, it can have 32 realizations (instead of 24 on the plane). In the 7vertex case, there are two nontrivial graphs with 64 realizations (instead of 48 and 56 respectively on the plane),see Figure 5.5. Let us indicate that 64 realizations can be also achieved by the 3 graphs constructed by applying an H1 move on L 24 , since H1 doubles the number of embeddings. Observe that this contrasts the situation of the complex em beddings in the plane, since it is known that for |V | ≤ 12 there is always a unique Laman graph with the maximal number of complex embeddings on the plane among all Laman graphs with the same number of vertices [START_REF] Capco | The number of realizations of a Laman graph[END_REF]. We have also found edge lengths that max imize the spherical embeddings of L 136 (see Figure 5.4

Geiringer graphs

The method we introduced in Section 5.1.2 played a crucial role in increasing the number of embeddings of Geiringer graphs. We used our method for the only nontrivial graph with 6 vertices -the cyclohexane G 16 . It was known that r 3 (G 16 ) = 16, a result that can be verified by our method within a few tries with random starting lengths.

The case of |V | = 7 was the first open one. There are twenty trivial 7vertex Geiringer graphs and six nontrivial ones. We computed the mixed volumes and the number of complex embeddings for each one of them. Then, using our code we were able to find edge lengths that give a full classification of all 7vertex Geiringer graphs according to r 3 (G) [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF].

We want to remark again at this point that G 48 was the model for our coupler curve method.

Using our implementation, we were able to find lengths that maximize the number of em beddings only after a few iterations. The structure of this graph fits perfectly to our method, They can be found from the starting edge lengths given in Sec. 5.1.2 with 28 real em beddings in only 3 iterations, using the subgraphs

(v 5 , v 6 , v 1 , v 7 , v 4 ), (v 4 , v 3 , v 1 , v 7 , v 5 ) and (v 3 , v 2 , v 1 , v 7 , v 4 ).
We repeated the same procedure for |V | = 8. In that case we can use the H1 doubling property for 311 graphs, while there are 63 graphs with a nontrivial number of embeddings. We computed complex bounds for all nontrivial graphs [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF]. We subsequently found edge lengths that increase the number of real embeddings of G 160 , which is the graph with the maximal number of complex embeddings c 3 (G 160 ) = 160. We were able to find parame ters λ such that r 3 (G 160 , λ) = 132.

The following lengths give 132 real embeddings for G 160 : One may find a full list of Geiringer graphs with 7 and 8 vertices in [START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF].

λ 1,2 = 1.

Lower bounds

The maximal numbers of real embeddings that we found can serve to build an infinite class of bigger graphs. These frameworks can give us lower bounds on the maximum

G ′ = (V G ′ , E G ′ ).
We construct a rigid graph using l copies of G, where all the copies have the subgraph G ′ in common. The new graph is rigid, has

|V | = |V G ′ | + l(|V G | -|V G ′ |)
vertices, and the number of its real embeddings is at least

2 (|V |-|V G ′ |) mod (|V G |-|V G ′ |) • r d (G ′ ) • r d (G) r d (G ′ ) |V |-|V G ′ | |V G |-|V G ′ | .
Remind that for a triangle T we have that r 2 (T ) = r S 2 (T ) = 2, while r 3 (T ) = 1. For Laman graphs, the best asymptotic bound is derived from L 880 :

Corollary 6

The maximum number of real embeddings on the plane among Laman graphs with n vertices is bounded from below by

2 (|V |-3) mod 7 • 2 • 430 ⌊(|V |-3)/7⌋ .
The bound asymptotically behaves as 2.3780 |V | .

The previous lower bound in that case was 2.3003 |V | by [START_REF] Emiris | The assembly modes of rigid 11bar linkages[END_REF].

In the case of spherical embeddings, we may use L 24 :

Corollary 7 The lower bound for the maximum number of spherical embeddings among Laman graphs with |V | vertices is

2 (|V |-3) mod 7 • 2 • 16 ⌊(|V |-3)/3⌋ .
This bound asymptotically behaves as 2.5198 |V | .

We remark that L 48H1a and L 48H2 , which have the 4vertex ). Notice that we use a subgraph with one embedding and not with two, as we did in the cases of Laman graphs. This happens because there is no tetrahedron as a subgraph of the 8vertex graphs that could give a better lower bound.

In Table 5.1, we compare the existing asymptotic lower bounds on the maximal real em bedding number, with the improvements presented in this chapter.

CONCLUSION AND OPEN QUESTIONS

In this thesis we have developed various methods concerning bounds on the embedding number of minimially rigid graphs. We presented new methods to compute efficiently the mBézout bound of the complex embedings of minimally rigid graphs using graph orien tations and matrix permanents. These bounds are graphspecific. We also compared our experimental results with existing ones indicating that some classes of graphs have tight mBézout bounds. Motivated by these results, we applied Bernstein's second theo rem in the case of the mBézout bound for rigid graphs. Our findings in this topic can be generalized for every class of polynomial systems that have no zero solutions.

In order to improve general upper bounds on the embedding number, initially we exploited existing bounds on planar graph orientations and matrix permanents. This led to improve ments on the asymptotic upper bounds of the embeddings for planar graphs in dimension 3 and for all graphs for d ≥ 5. Then, we introduced a method that bounds the number of outdegree constrained eliminations that are related to the mBézout bound, as stated above. This method resulted in a new bound for the embeddings of all minimally rigid graphs with a given number of vertices, which was generalized as the first nontrivial up per bound in the cases of Laman and Geiringer graphs. It also improved bounds in all dimensions bigger than 3, including our own results.

Finally, we have developed and used efficient methods to maximize the number of real embeddings of rigid graphs in the case of planar, spherical and spatial embeddings. In this context a new technique inspired by coupler curves was introduced for Geiringer graphs. These methods led to a classification of certain Laman and Geiringer graphs up to their real embedding number and to an improvement of the asymptotic lower bounds on the maximal number of embeddings. These increased lower bounds combined with the ameliorated upper bounds found in this thesis, reduce the existing gap between them.

Several open questions rise from our results. First of all, the gap between upper and lower bounds remain (even in the case of lower bounds on the maximal complex embed ding number which is easier to compute and was not treated in this thesis). In this context, it would be useful to investigate how sharp our upper bound is on the number of pseudo graph orientations and, subsequently, on the maximal complex embedding number. Both of these may require large computational resources.

Besides that, finding the minimal mBézout bound requires the computation of bounds up to all possible choices for a fixed K d . Thus, it would be convenient to find a method to select the K d that attains the minimum without computing its bound. Another issue is that the elimination process may result to a more efficient algorithm for the computation of the outdegreeconstrained orientations. The worst case scenario of our recursive algorithm is ∼ 2 |E| , while the bound on orientations is in the order of ∼ ζ Regarding the exactness of the mBézout bound and the application of Bernstein's sec ond theorem, the first priority would be a possible proof (or refutation) of Conjecture 1. This may help to investigate a possible relation between planarity and tight upper bounds, especially in the case of Geiringer graphs. Another issue is to optimize this method using the appropriate tools. A first idea is to construct resultant matrices that exploit the multi homogeneous structure (see for example [START_REF] Emiris | Multihomogeneous resultant formulae for systems with scaled support[END_REF][START_REF] Dickenstein | Multihomogeneous resultant formulae by means of complexes[END_REF]). The rank of the matrix could indicate which zero evaluations have solutions for our systems.

In the case of maximal real embeddings, the next step would be to ameliorate the maximal real bounds in all cases. One of the issues is the time needed to solve the systems of equations for bigger graphs, which is multiplied by the fact that more sampling iterations are necessary. For instance, our result for the 8vertex Geiringer graph is the best one obtained from running the coupler curve method for several weeks, with various starting points. In the case of Laman graphs, we faced the problem that homotopy solvers like phcpy are not always able to track all solutions when c d (G) is very big (> 1000 solutions for minimally rigid graphs). A more delicate approach uses geometrical tools to establish upper bounds (see details in [START_REF] Cox | Polytopes, resultants, and equations[END_REF]).

ABBREVIATIONS ACRONYMS

Definition 7 (Newton Polytope) Let a polynomial

f (x) = α∈Z m c α • x α ∈ C[x]
where c α ∈ C * are the nonzero coefficients and x α = m i=1

x α i i for a vector α = (α 1 , . . . , α m ). Then the Newton Polytope of f is the convex hull of the exponent vectors α and will be denoted with NP(f ).

A basic operation that forms a new polytope from two or more old ones is the Minkowski sum.

Definition 8

Let Q 1 and Q 2 be two polytopes in R m . Then the minkowski sum

Q 1 + Q 2 is a new polytope such that Q 1 + Q 2 = {q 1 + q 2 : q 1 ∈ Q 1 and q 2 ∈ Q 2 }
Notice that the Minkowski Sum of polytopes lying in complementary subspaces is the same as the cartesian product of these polytopes.

Minkowski sum is used to define the mixed volume for a collection of polytopes.

Definition 9

The mixed volume of a collection of polytopes Q 1 , Q 2 , . . . , Q m ∈ R m is defined by the coefficient of the monomial

µ 1 • µ 2 • • • µ m in the polynomial Vol m (µ 1 Q 1 + • • • + µ m Q m ),
where Vol m is the mdimensional volume and will be denoted by MV m (Q 1 , . . . , Q m ). An equivalent method to compute the mixed volume is the following formula:

MV m (Q 1 , . . . , Q m ) = m j=1 (-1) m-j I⊂{1,2,...,m} |I|=j Vol m i∈I Q i (A.2)
There is a connection between the mixed volume of Newton Polytopes and the number of roots for a polynomial in the corresponding toric variety. The toric variety is a projective variety defined essentially by the Newton Polytopes of the given system and contains the topological torus (C * ) m as a dense subset. The settheoretic difference of a toric variety and (C * ) m is toric infinity in correspondence with projective infinity.

Theorem 16 (BKK theorem [START_REF] Bernstein | The number of roots of a system of equations[END_REF][START_REF] Khovanskii | Newton polyhedra and the genus of complete intersections[END_REF][START_REF] Kouchnirenko | Polyèdres de Newton et nombres de Milnor[END_REF]) Let f (x) as defined above, and let (NP(f i )) 1≤i≤m be the collection of Newton Polytopes for this polynomial system. Then, if the number of system's solutions in (C * ) m is finite, it is bounded above by the mixed volume of these Newton Polytopes. In general and without paying much attention to the underlying variety, we have the fol lowing relations as in [START_REF] Sommese | The Numerical Solution of Systems of Polyno mials Arising in Engineering and Science[END_REF]:

#real solutions ≤ #complex solutions ≤ mixed volume ≤ mBézout ≤ Bézout.

On the other hand, the complexity of computing bounds goes in the opposite direction. More precisely, the computation of the mBézout bound is #Phard by reduction to the permanent. The same hardness result holds for mixed volume, although for most polyno mial systems the runtime in practice is much bigger than the mBézout computation. An additional problem in the case of the mBézout is to discover the optimal variable partition minimizing this bound for a given polynomial. This problem is not in APX, unless P=NP [START_REF] Malajovich | Computing minimal multihomogeneous bezout numbers is hard[END_REF].

The Newton Polytopes capture the sparseness of the polynomials. In fact the Bézout and the mBézout bound can be also related with polytopes whose mixed volume gives these bounds. More precisely, the polytopes related to the Bézout bound are simplices, while the polytopes related to the mBézout bound are simplices or products of simplices (see [START_REF]How many zeroes? Counting the number of solutions of systems of polynomials via geometry at infinity[END_REF] for details). Let us give an example of the bounds and their polytopes.

Example 7 We will consider the following polynomial system in two variables.

f 1 (x 1 , x 2 ) = x 3 1 + x 2 2 -3 f 2 (x 1 , x 2 ) = x 1 + x 2 2 x 1 + x 2 2 + 5
The Bézout bound of this system of equations is 3 • 3 = 9.

Let us compute the mBézout bound for the trivial partition X 1 = {x 1 }, X 2 = {x 2 }. Obvi ously |X 1 | = |X 2 | = 1, so we need to find the coefficient of Y 1 • Y 2 in the polynomial It is not a surprise that the BKK bound and the mBézout bound coincide. If we study the structure of the polytope NP(f 1 ) we may see that it is a simplex, so it is related with dense polynomials and correspond also to both the Bézout and the mBézout bound. In the case of NP(f 2 ) we have the cartesian product of two 1simplices {(0, 0), (1, 0)} × {(0, 0), (0, 2)}, showing that the multidegree vector (1, 2) of this polynomial is equivalent with the Newton Polytope. On the other hand a dense polynomial with degree 3 would have as Newton Polytope the convex hull of a simplex, such that one of the coordinate for at least one vertex shall be 3, e.g. {(0, 0), (1, 0), (0, 3)}, indicating that the Bézout bound shall be higher (See It is obvious that if the polytopes associated with the Bézout or the mBézout bound co incide with the Newton Polytopes, then the bounds also coincide. On the other hand this is not a necessary condition for equal bounds, as in the case of sphere equations (see Section 3.2).

(3Y 1 + 2Y 2 ) • (Y 1 + 2Y 2 ) = 3Y 2 1 + 8Y 1 Y 2 + 4Y
The exactness of the BKK bound can be verified by Bernstein's discriminant conditions. In order to state these conditions we first need the following definition. Then the initial form f w is a polynomial consisting of all the monomials whose exponent vectors belong in A ′ :

f w (x) = α ′ ∈A ′ c α ′ • x α ′ .
Since the initial form f w contains precisely the monomials whose exponent vector min imizes the inner product with w and excluding the others, we can relate w to an inner vector of a face of NP(f ). Hence, the algebraic system comprised of initial forms for a face normal w shall be called face system.

The necessary and sufficient condition of BKK exactness is stated below.

Theorem 17 (Bernstein's second theorem [START_REF] Bernstein | The number of roots of a system of equations[END_REF]) Let f be a system of polynomials as de fined above

Q = m i=1 NP(f i ) (A.3)
be the Minkowski sum of their Newton Polytopes. The number of solutions of f in (C * ) m equals exactly its mixed volume (counted with multiplicities) if and only if, for all w ∈ R m , such that w is a face normal of Q, the system of equations (f w i ) 1≤i≤m has no solutions in (C * ) m .

Let us note that although there is an infinite number of vectors that may appear as inner normals, Bernstein's condition can be verified choosing only one inner normal vector for every different face of Q. This theorem can also verify the exactness of the Bézout or the mBézout bound, if the Minkowski sum of polytopes related to these bounds is taken into account instead of the Minkowski sum of Newton polytopes (see Equation A.3).

APPENDIX B. THE COMPUTATION OF THE EMBEDDING NUMBER USING SPHERE EQUATIONS IN THE ABSENCE OF K d .

In Section 2.2 we introduce sphere equations and explain that the embedding number is the number of solutions derived from this system if all the coordinates of a complete graph in d vertices are fixed, following [START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF][START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. Although in dimension 2 there can always be a fixed edge (or K 2 ), in bigger dimensions this condition is not guaranteed. For example, in most known cases of Geiringer graphs, there is a fixed triangle, but there exist minimally rigid graphs with no triangles: K 6,4 is the only instance with up to 10 vertices. We have not constructed as many graphs in bigger dimensions using Henneberg steps, as in dimen sions 2 and 3 (see Table 2.1), but we can verify that the graphs with no complete subgraph K d are more for d ≥ 4. In this Appendix we will analyze how to compute the embedding number using sphere equations in the absence of a clique. Note that this case does not affect the asymptotic bounds presented in Chapter 4 and that all Geiringer graphs treated in Chapter 5 posses at least one triangle. We also remark that no such clarification is needed for the CayleyMenger semialgebraic systems, since in that case the solutions of the system correspond to distance coordinates and not to usual euclidean ones.

Maxwell's condition subtracts the dof of trivial motions (rotations and translations) from the total number of coordinates for an embedding of a graph G(V, E) in R d , as explained in Chapter 1. Fixing the number of coordinates corresponding to the dof yields already a 0-dimensional algebraic system using Edge Equations 1.1, or the sphere equations. On the other hand, the solutions of such system correspond to multiple embeddings up to trivial motions. Before explaining that statement we need the following proposition. This proposition is trivial, since a graph K d can be embedded as a (d -1)-dimensional simplex.

Let us now demonstrate how we treat the algebraic system in the case of Laman graphs, before generalizing this process to higher dimensions. Let K 2 be a complete graph with vertices {u, v}, or simply an edge, and λ u,v be an edge labeling. Maxwell's condition in dimension 2 indicates that we shall subtract 3 coordinates, so we can set u(0, 0) and v(0, y). Now it is clear that the ycoordinate of v can have two solutions, that are y = ±λ u,v (See Figure B.1). These solutions evidently correspond to the same embedding, if we factor out rigid motions. Thus, if we also fix the second coordinate of v, then there is only one possible embedding for K 2 and by fixing the coordinates of that edge in a bigger Laman graph, the number of solutions of sphere equations is the same as the embedding number. Notice that the existence of the edge allows us to fix the additional coordinate. (u, v). Then, we use Maxwell's condition to remove 6 degrees of freedom as follows: first we define a plane on which all three vertices lie by fixing one of their coordinates e.g. x = 0 for all three, removing 3 dof, and then we fix the other 2 coordinates of u and 1 more coordinate of v removing the 3 remaining dof. An additional dof is removed using the edge, fixing the third coordinate of v. Now the first vertices u and v are fixed, while w is partially fixed. The corresponding algebraic system counts every embedding twice (by reflection on the plane defined above). Notice that if we had not fixed the third coordinate of v, then there would be two solutions of the algebraic system for the embedding of the edge (u, v), as in the 2-dimensional case, so in total this algebraic system would count every embedding four times. These relations can apply to the computation of a bound on the embeddings using the methods from Chapter 3 on a system of sphere equations as described above. More precisely, let us denote with B(G, K d ′ ) the orientations of a graph G\E(K d ′ ) such that the outdegree of each vertex equals its dof, then the embedding number is bounded by Similarly, we can construct the mBézout matrix A by adding blocks of rows associated to the partially fixed vertices. The number of each block equals to the dof of each one of these and the bound is computed by the following relation:

2 |V |-d • B(G, K d ′ ).
d-d ′ i=1 1 d ′ -1 + i • 2 d! |V |-d
• per(A).

In that case, the size of square matrix the A is d • n × d • n, where n is the same as above.

4. 1 A

 1 pseudograph with 6 vertices. The extended degrees are the following: (3, 1) for vertices 1, 2, 4, 5, (3, 0) for vertex 6, and (4, 1) for vertex 3. . . . . . 4.2 Elimination of a vertex with extended degree (a) (3, 0), encountered in ver tex elimination, or (b) (3, 1), encountered in path elimination. In (a) there are 3 choices for eliminating edges, resulting in 3 different pseudographs; in (b) there are 2 choices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Two choices after eliminating a (3, 1)path of length ℓ = 3 respecting the edge count; ℓ -1 hanging edges get eliminated. . . . . . . . . . . . . . . . 4.4 A pseudograph L(V, E, H) and the blockcut tree of its normal subgraph G(V, E). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 After removing a fixed edge (vertical dashed blue) from a Laman graph, one gets a pseudograph with 2 connected components. . . . . . . . . . . . . . 4.6 (a) Two Laman graphs, Desargues' and K 3,3 , both resulting in the same pseudograph for some fixed edge. (b) Choosing a different fixed edge for Desargues' graph results in a different pseudograph. . . . . . . . . . . . . 4.7 Elimination of a (4, 2)path (with length ℓ = 2) in the case of orientations with fixed outdegree 3. This elimination is analogous to that in Figure 4.3. . 5.1 Coinciding vertices v 7 and v 8 of G 160 results in G 48 . . . . . . . . . . . . . . .

  e. a map from the set of vertices V to R d . The pair of a simple undirected graph G and an embedding ρ is also known as bar framework (or simply framework) and is usually denoted with G(ρ). Every such framework induces a set of edge lengths λ = {λ u,v | (u, v) ∈ E} such that λ u,v = ρ u -ρ v , where • denotes the usual euclidean norm.

  A direct application of Bézout's bound in the system of squared distance equations 1.1 results to O(2 d•|V | ) as an asymptotic upper bound for c d (|V |) (and conse quently for r d (|V |)), taking into account Maxwell's condition for the cardinality of the system of equations. This bound will be called Bézout bound in the rest of this text.

Figure 2 . 1 :

 21 Figure 2.1: Henneberg steps for Laman and Geiringer graphs.

  Let a Laman graph G |V |+1 be constructed by an H1 move applied to G |V | with |V | ver tices, whose extended globally rigid graph is J |V | . Without loss of generality, this move

Figure 2 . 2 :

 22 Figure 2.2: J |V |+1 is constructed by an H1 step applied to J |V | (blue edges), extended with the edge (u, v |V |+1 ). This is equivalent with applying an H2 step and adding the deleted edge (u, v |V |+1 ).

Algorithm 1 :

 1 Count graph orientationsFunction(orient) Input: |V | (# of vertices), E (graph edges without E(K d )), outdeg (desired outdegree list. If vertex u ∈ V (K d ) then outdeg[u] = 0, otherwise outdeg[u] = d). Output: # of outdegreeconstrained orientations deg = vertex degrees of graph G(V, E) /* Ending condition for the recursion */ if |E| = 0 then return (1) /* No valid orientations in this case */ if ∃u, outdeg [u] > deg [u] or outdeg [u] < 0 then return (0) /* Examine the conditions yielding unique orientations */ for u ≤ |V | do if outdeg[u] = 0 // u admits only new indirerected edge orientations then for all edges

Theorem 5

 5 Let G(V, E) be a minimally rigid graph in C d and P G be the Minkowski sum defined above. The set of the inner normal vectors of the facets of P G are exactly • all unit vectors e i , and• the |V | -d vectors of the form δ u = d+1 j=1e (d+1)•(u-1)+j = (0, 0, . . . , -1, -1, . . . , -1, . . . , 0),

  u∈V ′ (deg(u) + 2) • ∆ d+1 , where ∆ d+1 is the unit (d + 1)simplex 1 . The inner normal vectors of the facets of ∆ d+1 in R d+1 are the unit vectors e i and δ = d+1 j=1

Theorem 6

 6 (d+1)•(|V |-d) •(2 (|V |-d) -1) checks, but using Corollary 4 one needs to verify the zero evaluations of δvariables for all choices of δvariables. The latter, can be further reduced from d |V |-d to d |V |-d-1 , due to the fact that the coordinate variables are symmetric. Summarizing, when checking Bernstein's condition, for any of the d |V |-d-1 choices of δvariable transformation that construct F (t), it suffices that |V | -d zero evaluations should be applied for each of the δvariables. Bernstein's condition can be verified in the case of the sphere equations after checking a total of at most (|V | -d) • d |V |-d-1 face systems.

Function(IsmBezoutOfGraphExact) 1 F

 1 Input: F (sphere equations), V ′ (nonfixed vertices), Conjecture (If True, only one choice of F , else all choices of F ) Output: True (mBézout= c d (G)) or False (mBézout> c d (G)) /* Verification of Bernstein's condition */ if Conjecture=True then /* Transformation to F (t) */ L = [1, 1, . . . , 1] // L length = number of u ∈ V ′ F =ConstructDeltaPoly(F,V',L) /* Check for zero solutions of δ-variables (main computation) */ for u ∈ V ′ do /* Check if zero evaluation has solutions using ideal of transformed face system */ if F (t, {t u,lu = 0}) has a solution then return (False) else if Conjecture=False then for all choices of 1 out of d variables in every X u , u = 1 do L = [1, (l u , u ∈ V ′ \{1})] // always same choice for X =ConstructDeltaPoly(F,V',L) /* Check for zero solutions of δ-variables (main computation). */ for u ∈ V ′ do 21 if F (t, {t u,lu = 0}) has a solution then 22 return (False) return (True)

Figure 3 . 3 :

 33 Figure 3.3: Desargues graph (double prism).

Figure 3 . 4 :

 34 Figure 3.4: The JacksonOwen graph

  Conjecture 1 holds, then one only needs to check |V |-d face systems that correspond to the zero evaluations of F (t) for each one of the δvariables, instead of the (|V |-d)•d |V |-d-1 face systems indicated in Theorem 6. Algorithm 2 includes the option to consider the Conjecture 1 to be either True or False. The first option takes into consideration only one choice of δvariables, while in the second one all different choices of δvariables are checked, as in Theorem 6.

Theorem 7

 7 Planar Geiringer graphs have at most O 7.1131 |V | embeddings.

Theorem 8

 8 For d ≥ 5 the Bézout bound is strictly larger than the mBézout bound given by Equation (3.5) for any fixed K d . Given a fixed dimension d, the asymptotic upper bound derived from the BrègmanMinc inequality is In this proof Be d (|V |) and mBe d (|V |) denote the Bézout and the maximal m Bézout bound of minimally rigid graphs in C d with |V | vertices respectively. Since the number of edge equations for minimally rigid graphs with |V | vertices is |V

. 3 )

 3 Combining these bounds we get a sufficient condition for Be d (|V |) > mBe d (|V |):

Figure 4 . 1 :

 41 Figure 4.1: A pseudograph with 6 vertices. The extended degrees are the following: (3, 1) for vertices 1, 2, 4, 5, (3, 0) for vertex 6, and (4, 1) for vertex 3.

Proposition 3

 3 Let L(V, E, H) be a pseudograph with a valid orientation. Then |H|+|E| = 2|V |. Proof: |H| + |E| is the sum of outdegrees over all edges; 2|V | equals the sum of outde grees over vertices. □

Figure 4 . 2 :

 42 Figure 4.2: Elimination of a vertex with extended degree (a) (3, 0), encountered in vertex elimination, or (b) (3, 1), encountered in path elimination. In (a) there are 3 choices for eliminating edges, resulting in 3 different pseudographs; in (b) there are 2 choices.

Figure 4 . 3 :

 43 Figure 4.3: Two choices after eliminating a (3, 1)path of length ℓ = 3 respecting the edge count; ℓ -1 hanging edges get eliminated.

Proposition 6

 6 Let L(V, E, H) be a connected pseudograph such that G(V, E) is a tree. Then 1. The number of valid orientations for L is either 1 or 0; 2. If L has a valid orientation, then k = n + 1; E. Bartzos where n = |V | and k = |H|.

Figure 4 .

 4 5, this construction leads to a pseudograph with two connected components. Remark that the number of vertices n of L G,e is related to the number of vertices of G by n = |V | -2.

Figure 4 . 5 :

 45 Figure 4.5: After removing a fixed edge (vertical dashed blue) from a Laman graph, one gets a pseudograph with 2 connected components.

Figure 4 . 6 :

 46 Figure 4.6: (a) Two Laman graphs, Desargues' and K 3,3 , both resulting in the same pseudograph for some fixed edge. (b) Choosing a different fixed edge for Desargues' graph results in a different pseudograph.

Lemma 6

 6 respectively the numbers of vertices and of hanging edges per connected component with strictly more than one vertex. The bound follows from Theorem 9, since n ≥ µ ′ i=1 n i and k ′ = µ ′ i=1 k i . □ Let G(V, E) be a Laman graph, and L G,e , k ′ and µ ′ as above. Then k ′ ≥ 3µ ′ .

If we replace ( 3 , 1 )

 31 paths in Proposition 5 by (d + 1, d -1)paths, we have an analogous result, since (d + 1, d -1)vertices have normal degree 2. This implies that there is al ways an elimination process preserving connectivity. Moreover, the necessary count in Proposition 3 is generalized to |E| + |H| = d • |V | for every pseudograph L(V, E, H) with at least one orientation with fixed outdegree d; such orientations extend the notion of validity beyond d = 2.

Figure 4 . 7 :

 47 Figure 4.7: Elimination of a (4, 2)path (with length ℓ = 2) in the case of orientations with fixed outdegree 3. This elimination is analogous to that in Figure 4.3.

all ℓ ≥ 2 .

 2 In the second case the equalities are achieved with ζ d = 2 d-1 , ε d = 1/2 for all ℓ. The same (ζ d , ε d )point gives equality in (4.12) for (p, d) ∈ {(d, d -1), (d + 1, d)}. By taking the logarithm, (4.12) and (4.13) become linear in the (ln ζ d , ln ε d )plane. The corresponding lines have negative slope and contain point ((d -1) ln 2, -ln 2); the one defined by (4.13) for ℓ = 2 is closest to the vertical. So the corresponding inequalities are dominated for ζ d ≤ 2 d-1 by (4.13) with ℓ = 2.

Figure 5 . 1 :

 51 Figure 5.1: Coinciding vertices v 7 and v 8 of G 160 results in G 48 .

Figure 5 . 3 :

 53 Figure 5.3: The coupler curve C v 6 ,λ of G 48 with the edge v 2 v 6 removed. The 28 red points are intersections of C v 6 ,λ with the sphere centered at v 2 with the edge lengths λ, whereas the 32 green ones are for the adjusted edge lengths (illustrated by blue dashed lines).

Figure 5 . 4 :

 54 Figure 5.4: Laman graphs with maximal numbers of complex embeddings with 8 ≤ |V | ≤ 10. We have found tight bounds for |V | = 8 and |V | = 9.

2 ) 2 )Figure A. 1 :

 221 Figure A.1: The Newton Polytopes of the polynomials in Example 7

Figure A. 2 :

 2 Figure A.2:The Newton Polytope of a dense polynomial with total degree 3.

Figure

Definition 10 (

 10 Initial form and face system) Let w be a vector in R m and f (x) = α∈A c α • x α be a polynomial in C[x], where A consists of the exponent vectors of monomials with nonzero coefficients. Let A ′ be the subset of vectors in A, such that α ′ ∈ A ′ ⇐⇒ α ′ , w = min α∈A ( α, w ).

Proposition 7

 7 The embedding number of a complete graph in d vertices up to rigid mo tions in R d (or C d and S d ) is 1.

For d = 3 ,Figure B. 1 :

 31 Figure B.1: Fixing 2 coordinates for vertex u and 1 coordinate for vertex v, there are two possible embeddings for the latter. Both embeddings are equivalent up to trivial motions in R 2 .

  Generally, if for a minimally rigid graph G(V, E) in d ≥ 3 no K d exists, a maximal clique may be fixed with d ′ < d vertices and for the rest d -d ′ vertices one may fix an appropriate number of coordinates, thus factoring out rotations and translations according to Maxwell's condition. More precisely we can have the following cases:• d ′ fixed vertices v 1 , . . . , v d ′ with no dof. • d -d ′ partially fixed vertices v ′ 1 , v ′ 2 , . . . , v ′ d-d ′ with d ′ , d ′ + 1, • • • , d -1 dof respectively. • |V | -d nonfixed vertices u 1 , . . . , u |V |-d with d dof.Clearly, d ′ ≥ 2 since an edge always exists.Let now S(G, λ, K d ′ (ρ)) denote the solutions of sphere equations for the embedding of a graph in C d and S R (G, λ, K d ′ (ρ)) the real solutions in R d , up to a fixed embedding K d ′ (ρ) for a generic choice of edge lengths λ. Then we have the following relations between the number of solutions and the embedding number:|S(G, λ, K d ′ (ρ))| = 2 d-d ′ • c d (G) and |S R (G, λ, K d ′ (ρ))| = 2 d-d ′ • r d (G, λ) (B.1)

  Notice that the number of vertices for the corresponding pseudograph are bounded by the inequality|V | -d ≤ n ≤ |V | -2, since n = |V | -d + d ′ .

  . Επιπλέον βελτιώνουν τα υπάρχοντά κάτω φράγματα του μέγιστου αριθμού διαμορφώσεων σε Ω 2.3780 |V | στο επίπεδο, Ω 2.5198 |V | στην σφαίρα S 2 και Ω 2.6553 |V | στον χώρο.

	ΘΕΜΑΤΙΚΗ ΠΕΡΙΟΧΗ: Θεωρία Άκαμπτων Γράφων
	ΛΕΞΕΙΣ ΚΛΕΙΔΙΑ: Ελαχιστικώς Άκαμπτος Γράφος, Πολυομογενές Φράγμα Bézout,
	Γεωμετρία Αποστάσεων, Ασυμπτωτικό Όριο, Μεικτός Όγκος

  Minc. Συγκεκριμένα, για τις πιο ενδιαφέρουσες κλάσεις γράφων, αποδείξαμε ότι οι Laman γράφοι έχουν το πολύ O 3.7764 |V | διαμορφώσεις, ενώ οι Geiringer γράφοι έχουν το πολύ O 6.8399 |V | διαμορφώσεις, ενώ τα προϋπάρχοντα φράγματα ήταν της τάξης του O 4 |V | και O 8 |V | αντίστοιχα.

(On the multihomogeneous Bézout bound of the embedding number).

  Ως εκ τούτου, παρουσιάζουμε μια πλήρη κατηγοριοποίηση των Ε.Α.Γ. ως προς τον μέγιστο αριθμό διαμορφώσεων κάθε γράφου με |V | ≤ 7 στις περιπτώσεις των R 2 και R 3 , ενώ στην περίπτωση της σφαίρας αυτή η κατηγοριοποίηση αφορά τους γράφους με |V | ≤ 6. Σε όλες τις κατηγορίες βρίσκουμε κάτω όρια και για επιλεγμένους μεγαλύτερους γράφους. Σημειώνουμε ότι προηγουμένως δεν είχαν υπάρξει μελέτες που να αντιμετωπίζουν το συγκεκριμένο ερώτημα για την περίπτωση της σφαίρας. Επιπλέον, διαλέγοντας συγκεκριμένους γράφους με βάση τον αριθμό των μιγαδικών διαμορφώσεων, καταφέρνουμε να αυξήσουμε τα ασυμπτωτικά κάτω όρια σε κάθε μία από τις εξεταζόμενες περιπτώσεις. Συγκεκριμένα, στην περίπτωση του επιπέδου δείχνουμε ότι υπάρχουν γράφοι με Ω(2.3780 |V | ) διαμορφώσεις στο επίπεδο, Ω(2.5198 |V | ) διαμορφώσεις στην σφαίρα και Ω(2.6553 |V | ) διαμορφώσεις στον χώρο. Παρουσιάζονται οι μέθοδοι για τον υπολογισμό του Π.Α.Φ. Bézout των σφαιρικών εξισώσεων, καθώς και στοιχεία που συγκρίνουν τον υπολογιστικό χρόνο που απαιτείται για αυτές τις μεθόδους σε σχέση με το όριο τον υπολογισμό του μεικτού όγκου και του ακριβούς αριθμού των διαμορφώσεων. Στην συνέχεια, εξετάζονται πειραματικά δεδομένα ως προς την ακρίβεια του φράγματος και παρουσιάζεται μια μέθοδος που ελέγχει την ακρίβεια βασισμένη στο 2ο θεώρημα του Bern stein. Το περιεχόμενο αυτού του κεφαλαίου αποτελεί μέρος του

	Η διάρθρωση της διατριβής είναι η εξής:
	Κεφάλαιο 1 Εισαγωγή (Introduction). Ορίζονται βασικές αρχές της Θ.Α.Γ. Επίσης,
	περιγράφονται τα ερευνητικά θέματα που απασχολούν την διατριβή, καθώς και
	προϋπάρχουσες προσεγγίσεις σε αυτά.
	Κεφάλαιο 2 Βασικές έννοιες (Preliminaries). Γίνεται περιγραφή εργαλείων και εννοιών
	που θα χρησιμοποιηθούν στα επόμενα Κεφάλαια. Συγκεκριμένα, αρχικά περιγράφεται
	η μέθοδος Henneberg, που χρησιμοποιείται για την κατασκευή Ε.Α.Γ. Στην συνέχεια,
	παρουσιάζονται δύο μέθοδοι αλγεβρικής μοντελοποίησης για τις εμβυθίσεις των γράφων,
	οι σφαιρικές εξισώσεις και οι ορίζουσες των πινάκων CayleyMenger.

Κεφάλαιο 3 Το Π.Α.Φ. Bézout για τους Ε.Α.Γ.

  1.1 An example of a flexible an a rigid graph embedding. The fourbar linkage (a 1 , a 2 , a 3 ) is a flexible framework on the plane: pinning down the two bottom vertices to factor out trivial motions (for more details see Section 2.2.1) and moving the up right vertex in the direction of the flex results to a continuous deformation of the framework deformed satisfying the same edge lengths. Throughout the deformation from the left framework (a 1 ) to the right one (a 3 ) there is an infinity of realizations up to rigid motions. On the other hand, if an edge is added, then there are only two realizations up to rigid motions and reflections (b 1 and b

2 ) and there is no way to continuously deform this framework. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 The doublebanana graph is composed by two identical rigid components (blue and green) that are glued to two common vertices. Although this structure satisfies Maxwell's condition in R 3 , it is not rigid: its two rigid com ponents revolve in the space around the implied dashed axis that passes through the common vertices. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Henneberg steps for Laman and Geiringer graphs. . . . . . . . . . . . . . . 2.2 J |V |+1 is constructed by an H1 step applied to J |V | (blue edges), extended with the edge (u, v |V |+1

  The orientations of graphs L 56 and G 48 . Notice that there is only one way to direct the red edges up to the choice of K d (dashed blue). . . . . . . . .3.2The L 136 graph. The dashed edge is the fixed one. . . . . . . . . . . . . . .

). This is equivalent with applying an H2 step and adding the deleted edge (u, v |V |+1 ). . . . . . . . . . . . . . . . . . . . . . . .

2.3 The embeddings of the

Laman graph L 48H2 (grey edges) can be repre sented by submatrices of CM L 48H2 that involve only variables corresponding to the 4 red dashed edges. The extended graph is globally rigid. This con struction can be used to find also the spherical embeddings. . . . . . . . . 2.4 The graph G 48 (grey edges). There are submatrices of CM G 48 that involve only variables corresponding to the 3 red dashed edges of the left graph. The graph G 48 extended by the edge v 1 v 7 (that corresponds to the variable x 1 ) is globally rigid. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 3.3 Desargues graph (double prism). . . . . . . . . . . . . . . . . . . . . . . . . 3.4 The JacksonOwen graph . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Laman graphs with maximal numbers of spherical embeddings with 6 ver tices (L 24 Desargues graph with 32 spherical embeddings) and 7 vertices (L 48H1a ,L 48H1b ,L 48H1c ,L 48H2 and L 56 graphs with 64 spherical embeddings). Fixing 2 coordinates for vertex u and 1 coordinate for vertex v, there are two possible embeddings for the latter. Both embeddings are equivalent up to trivial motions in R 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Power basis of the existing asymptotic upper and lower bounds for mini mally rigid graphs in all embedding spaces treated. . . . . . . . . . . . . . . 2.1 Numbers of Laman and Geiringer graphs up to the last Henneberg move and graph planarity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	5.6 The 7vertex and 8vertex graphs with the maximal number of embeddings (G LIST OF TABLES 1.1

5.3 The coupler curve C v 6 ,λ of G 48 with the edge v 2 v 6 removed. The 28 red points are intersections of C v 6 ,λ with the sphere centered at v 2 with the edge lengths λ, whereas the 32 green ones are for the adjusted edge lengths (illustrated by blue dashed lines). . . . . . . . . . . . . . . . . . . . . . . . 5.4 Laman graphs with maximal numbers of complex embeddings with 8 ≤ |V | ≤ 10. We have found tight bounds for |V | = 8 and |V | = 9. . . . . . . . 5.5 48 and G 160 ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 The Newton Polytopes of the polynomials in Example 7 . . . . . . . . . . . 103 A.2 The Newton Polytope of a dense polynomial with total degree 3. . . . . . . 104 B.1 3.1 Runtimes of different algorithms on graphs with maximal c d (G) up to |V | = 11 and up to |V | = 10 for Laman and Geiringer graphs, respectively. We compute c 2 (G) by [16] and c 3 (G) by phcpy [8] (fails to find all solutions for |V | > 11). Also runtimes for computing c 2 (G), c 3 (G) by MonodromySolver. We compute mixed volume (MV) by phcpy, mBézout (mBe) by Maple's permanent and our Python code [6]. Computation of the mBézout and MV is up to a fixed K d (edges or triangles). . . . . . . . . . . . . . . . . . . . . 3.2 Mixed volumes, complex embedding numbers, and mBézout bounds for embeddings of Laman graphs in C 2 and S 2 . These graphs have the maxi mal number of embeddings in C 2 . The 12vertex maximal Laman graph is the first nonplanar in this category. . . . . . . . . . . . . . . . . . . . . . . . 4.1 Power basis of asymptotic upper bounds for minimally rigid graphs in C d : the first line contains the bounds derived in Section 4.1 applying Brègman Minc bound (BM), while the second those presented in Section 4.2 (pseu.), and Béz. corresponds to the trivial Bézout bound. . . . . . . . . . . . . . . 5.1 Power basis of asymptotic lower bounds for minimally rigid graphs in all em bedding spaces treated. The first line contains the existing lower bounds, while the second one the lower bounds presented here (there were previ ously no lower bounds for the real spherical case). . . . . . . . . . . . . . .

Table 1 .1: Power

 1 basis of the existing asymptotic upper and lower bounds for minimally rigid graphs in all embedding spaces treated.

	embedding	R 2	C 2	S 2 C	R 3	C 3
	space
	lower bound 2.3003 2.5079 2.5698 2.5198 3.0683
	upper bound	4	4	4	8	8

  On the other hand, a sequence of moves known as Henneberg steps can construct such sets of minimally rigid graphs in R d starting from the complete graph on d vertices K d[START_REF] Tay | Generating isostatic frameworks[END_REF] 1 .

	H1	H2	H1	H2	H3x	H3v
	2degree	edge split	3degree	edge split Xreplacement	double
	vertex addition	in 2d	vertex addition	in 3d		Vreplacement

Table 2 . 1 :

 21 Numbers of Laman and Geiringer graphs up to the last Henneberg move and graph planarity.

		Laman graphs
	n	3 4 5 6 7	8	9	10	11
	H1 planar	1 1 3 11 62 491 5, 041 60, 040 791, 195
	H1 nonplanar		4	85 1, 917 46, 903 1, 201, 401
	H2 planar	1	3	18	122	1, 037	9, 884
	H2 nonplanar 1	1	14	142	2, 152	36, 793
		Geiringer graphs
	n	4 5 6 7	8	9		10	11
	H1 planar	1 1 1 4	12	45		221	1, 215
	H1 nonplanar 2 16 299 9, 718 527, 250 41, 907, 790
	H2 planar	1 1	2	5		12	34
	H2 nonplanar 5	61 1, 719 85, 401	6, 267, 144

  since vertex u is fixed and no variables are assigned for it.

	This means that we only need to find the coefficient of the monomial	Y d u in the poly
	u∈V ′

nomial of the product (see Theorem 15 in Appendix A for details on the mBézout):

  The orientations of graphs L 56 and G 48 . Notice that there is only one way to direct the red edges up to the choice of K d (dashed blue). 56 has 56 complex embeddings in the plane and 64 embeddings on the sphere, while G 48 has 48 embeddings in C 3 (these numbers coincide also with the maximum number of real embeddings, see[START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF][START_REF] Gallet | Counting realizations of Laman graphs on the sphere[END_REF] and Section 5.2 ). The mixed volumes of the algebraic systems are 64 and 48 respectively. The dashed lines indicate the fixed edges of K d . The edge direction for any edge that includes a fixed vertex is always oriented outwards the nonfixed vertex. This yields a unique orientation up to the fixed K d , which is coloured in red for both graphs. The rest of the graph admits B(L 56 , K 2 ) = 2 orientations for L 56 , while the number of different orientations for G 48 is B(G 48 , K 3 ) = 3. So the mBézout bound is 2 7-2 • 2 = 64 for L 56 and 2 7-3 • 3 = 48 for G 48 .

	Let us demonstrate our method examining one Laman and one Geiringer graph.

2 |V |-d . □ Figure 3.1: Example 1 Here are two examples of this counting method in the case of L 56 graph in di mension 2 and G 48 in dimension 3, which are both 7vertex graphs (see Figure 3.1). Graph

L

Table 3 . 1 :

 31 Runtimes of different algorithms on graphs with maximal c d (G) up to |V | = 11 and up to |V | = 10 for Laman and Geiringer graphs, respectively. We compute c 2 (G) by

Table 3 . 2 :

 32 Mixed volumes, complex embedding numbers, and mBézout bounds for em beddings of Laman graphs in C 2 and S 2 . These graphs have the maximal number of embeddings in C 2 . The 12vertex maximal Laman graph is the first nonplanar in this category. for a vast majority of cases (all planar graphs up to 6 vertices, 64/65 7vertex planar graphs and 496/509 8vertex planar graphs). Notice that the m Bézout bounds for different choices of the fixed edge are, in general, different for planar Laman graphs.

	n	MV 2d c 2 (G) MV S 2 c S 2 (G) mBézout
	6	32	24	32	32	32
	7	64	56	64	64	64
	8	192	136	192	192	192
	9	512	344	512	512	512
	10	1536	880	1536	1536	1536
	11	4096	2288	4096	4096	4096
	12 15630 6180 15630	8704	15630
	minimum mBézout bound

  3,2 , t 4,1 , t 4,2 , t 5,1 , t 5,2 , t 6,1 , t 6,2 , t 7,1 , t 7,2 , t 8,1 , t 8,2 , t 8,3 }. As in the case of Desargues' graph, the evaluation of t 3,1 , t 4,1 , t 5,1 , t 6,1 , t 7,1 , t 8,1 to zero corresponds to the face systems of δ 3 , δ 4 , δ 5 , δ 6 , δ 7 , δ 8 respectively.

Table 4 .

 4

	d	2	3	4	5	6	7	8	9
	BM	4.8990 8.9442 16.733 31.749 60.795 117.17 226.89 441
	pseu. 3.7764 6.8399 12.686 23.899 45.533 87.469 168.90 327.45
	Béz. 4	8	16	32	64	128	256	512

1: Power basis of asymptotic upper bounds for minimally rigid graphs in C d : the first line contains the bounds derived in Section 4.1 applying BrègmanMinc bound (BM), while the second those presented in Section 4.2 (pseu.), and Béz. corresponds to the trivial Bézout bound.

  |V | to 2.3811 |V | for d = 2 and from 2.51984 |V | to 2.6390 |V | for d = 3, while they establish 2.51984 |V | as a lower bound for the number of embeddings in S 2 .

  and λ ′ e (t) = λ e for all e ∈ E G ′ \ {(u, v), (u, w), (u, q)} ,then the coupler curve C u ′ ,λ ′ (t) of u ′ w.r.t. the fixed triangle is the same for all t ∈ R + , namely, it is C u ′ ,λ . Moreover, if (u ′ , w) ∈ E, then C u ′ ,λ is a spherical curve.

  Using Matplotlib by[START_REF] Hunter | Matplotlib: A 2D graphics environment[END_REF], our program[START_REF] Bartzos | Graph embeddings in the plane, space and spheresource code and results[END_REF] can plot the coupler curve of the vertex v 6 of the graph G 48 \(v 2 , v 6 ) w.r.t. the fixed triangle v 1 v 2 v 3 , see Figure5.3 for the out put. There are 28 embeddings for λ. Following Lemma 7 for the subgraph given by (u, v, w, q, u ′ ) = (v 2 , v 3 , v 1 , v 7 , v 6 ), one can find a position and radius of the sphere corre sponding to the removed edge (v 2 , v 6 ) such that there are 32 intersections. Such edge lengths are obtained by taking λ 1,2 = 4.0534 , λ 2,7 = 11.1069 , λ 2,6 = 3.8545 , λ 2,3 = 4.0519.

	99993774567597 ,	λ 2,7 = 10.5360917228793 ,	λ 2,3 = 0.99961432208948 ,
	λ 1,3 = 1.99476987780024 ,	λ 3,7 = 10.5363171636461 ,	λ 3,4 = 1.00368644488060 ,
	λ 1,4 = 2.00343646098439 ,	λ 4,7 = 10.5357233031495 ,	λ 4,5 = 1.00153014850485 ,
	λ 1,5 = 2.00289249524296 ,	λ 5,7 = 10.5362736599978 ,	λ 5,6 = 0.99572361653574 ,
	λ 1,6 = 2.00013424746814 ,	λ 6,7 = 10.5364788463527 ,	λ 2,6 = 1.00198771097407 .

  .4. The following table summarizes the bound on r 2 (G) as well as c 2 (G) and the mixed volume for the two different algebraic systems. Notice that it shows that there exist edge lengths such that all embeddings of the 8vertex graph L 136 and of the 9vertex graph L 344 are real. Now, we provide edge lengths giving the numbers of real embeddings in the table.

		|V |	8	9	10
			L 136 L 344 L 880
	Mixed Volume of sphere eq. 192 512 1536
	Mixed Volume of distance eq. 136 344 880
		c 2 (G)	136 344 880
		r 2 (G) ≥	136 344 860*
	L 136 :	λ 1,2 = 1.000109994 ,	λ 1,4 = 1.000334944 ,	λ 1,8 = 1.000119993 ,
	λ 2,3 = 1.000174985 ,	λ 2,7 = 1.000379928 ,	λ 3,6 = 1.000459894 ,	λ 3,8 = 1.000099995 ,
	λ 4,5 = 1.000049999 ,	λ 4,7 = 1.000144989 ,	λ 5,7 = 1.000389924 ,	λ 5,8 = 1.000354937 ,
	λ 6,7 = 1.000244970 ,	λ 6,8 = 1.000289958 ,
	L 344 :	λ 1,4 = 1.00100 ,	λ 1,6 = 1.00046 ,	λ 1,9 = 1.00057 ,
	λ 2,3 = 1.00058 ,	λ 2,5 = 1.00075 ,	λ 2,8 = 1.00084 ,	λ 3,7 = 1.00073 ,
	λ 3,9 = 1.00042 ,	λ 4,7 = 1.00096 ,	λ 4,9 = 1.00015 ,	λ 5,7 = 1.00083 ,
	λ 5,8 = 1.00003 ,	λ 6,7 = 1.00086 ,	λ 6,8 = 1.00008 ,	λ 8,9 = 1.00039 ,
	L 880 :	λ 1,4 = 1.0002169 ,	λ 1,8 = 1.0001366 ,	λ 1,10 = 1.0004509 ,
	λ 2,3 = 1.000763 ,	λ 2,7 = 1.0000575 ,	λ 2,10 = 1.0006078 ,	λ 3,7 = 1.0001763 ,
	λ 3,9 = 1.00075 ,	λ 4,8 = 1.0008574 ,	λ 4,9 = 1.000536 ,	λ 5,7 = 1.000491 ,
	λ 5,8 = 1.0002946 ,	λ 5,10 = 1.0006778 ,	λ 6,7 = 1.0004699 ,	λ 6,8 = 1.0002724 ,
	λ 6,9 = 1.0005141 ,	λ 9,10 = 1.0003913 .

  ). It has 192 real spherical embed dings. We remark that there is again another 8vertex graph with 192 complex spherical embeddings, but we have found edge lengths with only 136 real spherical embeddings. 48H2 and L 56 graphs with 64 spherical embeddings).

	L 24 (Desargues) Figure 5.5: Laman graphs with maximal numbers of spherical embeddings with L 48H2 L 56 L 48H1a L 48H1b L 48H1c 6 vertices (L 24 Desargues graph with 32 spherical embeddings) and 7 vertices λ 1,2 = 1.43 , λ 1,4 = 1.39 , λ 1,6 = 1.055 , λ 2,3 = 1.45 , λ 2,5 = 1.193 , λ 3,4 = 1.388 , λ 3,5 = 1.64 , λ 4,6 = 1.691 , λ 5,6 = 1.386 , L 48H2 : λ 1,2 = 1.526433752 , λ 1,3 = 1.250599856 , λ 1,4 = 1.519868415 , λ 2,5 = 1.772004515 , λ 2,6 = 1.371860051 , λ 2,7 = 1.019803903 , λ 3,4 = 1.475127113 λ 3,7 = 1.363084737 , λ 4,6 = 1.314534138 , λ 5,6 = 1.754992877 , λ 6,7 = 1.054514106 , L 56 : λ 1,2 = 1.921665944 , λ 1,3 = 1.3 , λ 1,5 = 1.337908816 , λ 2,5 = 1.058300524 , λ 2,6 = 1.306139349 , λ 2,7 = 1.468332387 , λ 3,4 = 1.2 , (L 48H1a ,L 48H1b ,L 48H1c ,L L 24 : λ 3,7 = 0.6693280212 , λ 4,5 = 1.370401401 , λ 4,6 = 1.630337388 , λ 6,7 = 1.994993734 .

This table gives upper bound and the number of real spherical embeddings for all graphs with 6 ≤ |V | ≤ 8 that have the maximal number of embeddings. L 136 : λ 1,2 = 1.69431375697417 , λ 1,5 = 1.53147820126884 , λ 1,8 = 1.40741112578064 , λ 2,3 = 1.46514833488809 , λ 2,5 = 1.43532284310132 , λ 2,7 = 1.3673675423030 , λ 3,4 = 1.35543641920214 , λ 3,6 = 1.49080389256053 , λ 4,5 = 1.36622835551227 , λ 4,8 = 1.52724607627725 , λ 6,7 = 1.23765605522418 . λ 6,8 = 0.871783052046995 , λ 7,8 = 1.76892528306539 .

  The 7vertex and 8vertex graphs with the maximal number of embeddings (G 48 and G 160 ).since there are 20 subgraphs of G 48 given by vertices (u, v, w, q, u ′ ) satisfying the assump tion in Lemma 7. Using tree search approach, we obtained edge lengths λ such that r 3 (G 48 , λ) = 48:

		G 48	G 160
	Figure 5.6: λ 1,2 = 1.9999,	λ 1,6 = 2.0001,	λ 4,5 = 7.0744,	λ 4,7 = 11.8471,
	λ 1,3 = 1.9342,	λ 2,6 = 1.0020,	λ 5,6 = 4.4449,	λ 5,7 = 11.2396,
	λ 1,4 = 5.7963,	λ 2,3 = 0.5500,	d 2,7 = 10.5361,	λ 6,7 = 10.5365 .
	λ 1,5 = 4.4024,	λ 3,4 = 5.4247,	λ 3,7 = 10.5245,
			93	E. Bartzos

Table 5 . 1 :

 51 Power basis of asymptotic lower bounds for minimally rigid graphs in all em bedding spaces treated. The first line contains the existing lower bounds, while the second one the lower bounds presented here (there were previously no lower bounds for the real spherical case).

	embedding	R 2	S 2	R 3
	space
	previous	2.3003		2.5198
	new	2.3780 2.5198 2.6553
	number of embeddings. To compute the lower bound, we will use the following theorem
	that combines caterpillar, fan and generalized fan constructions [35]:

Theorem 13 Let G = (V G , E G ) be a generically rigid graph, with a generically rigid sub graph

  Laman graph as a subgraph, can give the same asymptotic lower bound. The other 7vertex graphs with r S 2 (L) = 64 can give only 2.3784 |V | as a lower bound, while the asymptotic bound from 8vertex graph with 192 embeddings is 2.4914 |V | .Finally, using the fact that r 3 (G 160 ) ≥ 132, we obtain the following result:The previous lower bound for Geiringer graphs was 2.51984 |V |[START_REF] Emiris | Computer Algebra Methods for Studying and Computing Molecular Conformations[END_REF][START_REF] Emiris | Mixed volume and distance geome try techniques for counting Euclidean embeddings of rigid graphs[END_REF]. Using the graph G 48 yields r 3 (|V |) ∈ Ω(2.6321|V |

	Corollary 8 The maximum number of real embeddings of Geiringer graphs with |V | ver
	tices can be bigger than
	2 (|V |-3) mod 5 132 ⌊(|V |-3)/5⌋ ,
	indicating that r 3 (|V |) ∈ Ω(2.6553 |V | ).

E.Bartzos

E. Bartzos

We also use this formulation and we call these systems sphere equations see Section 2.2 E.Bartzos

E. Bartzos

E.Bartzos

Recall from Chapter 1 that minimally rigid graphs in R d have the same property in C d , S d , S d C .

The technical details of the sphere equations in the absence of K d will be discussed in Appendix B. For simplicity, in the rest of this manuscript we assume the existence of a K d , unless stated otherwise.

E. Bartzos

The idea of using the product of polytopes is derived by a proof for the mixed volumes corresponding to the weighted mBézout bound in[START_REF]How many zeroes? Counting the number of solutions of systems of polynomials via geometry at infinity[END_REF]

Hanging edges are reminiscent of "directed loops" in hypergraphs[START_REF] Streinu | Sparse hypergraphs and pebble game algorithms[END_REF]; "halfedges" also have a single endpoint.

In[START_REF] Harary | Graph Theory[END_REF] Ch.

3] these subgraphs are called blocks; "biconnected component" is used equivalently, e.g.[START_REF] Jungnickel | Graphs, Networks and Algorithms[END_REF] Ch. 8].

E. Bartzos

for every connected component of L G,K d with at least d vertices.If n i ≤ d -1 we examine 2 different cases: (a) n i = 1 or 2 implying that the connected component has trivially one orientation, since the normal subgraph is either a single vertex, or a tree with 2 vertices. The number of hanging edges is k i = 2d -1, in order to respect the total edge count. (b) n i =

3, which implies d ≥ 4, then there should be ≤ 3 normal 83 E. Bartzos

In the sense that their minimal vertex degree is > 3, thus no H1 move is used in the final step of their construction and their embedding number cannot trivially deduced from a smaller graph. See Section

2.1 for details.

E. BartzosBounds on the maximal number of graph embeddings. E.Bartzos

E. Bartzos

E. Bartzos

E. Bartzos

ACKNOWLEDGEMENTS

I would like to give my warmest thanks for this thesis to my advisor Ioannis Emiris. First of all I thank him because he gave me the opportunity to enroll in a high quality PhD European

This thesis is part of the project ARCADES which has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska Curie grant agreement No 675789. It has been done at the Department of Informatics of the National and Kapodistrian University of Athens in collaboration with Athena Research and Innovation Centre.

We present a list of lengths (using euclidean metric) that give maximal number of realiza tions for the nontrivial cases:

APPENDIX A. ALGEBRAIC BOUNDS.

In this Appendix we present the main algebraic bounds used in this thesis. These bounds are established for projective spaces, but can be also applied for affine polynomials. These are the Bézout bound, the mBézout bound and the mixed volume bound (also known as BKK bound). We also give Bernstein's second theorem on the exactness of mixed volumes.

For the rest of this Appendix we will consider square polynomial systems

The first (and simplest) bound is the well known Bézout bound. Here we give a version for 0dimensional varieties in C m .

Theorem 14 (Bézout bound) Let α i be the total degree of a polynomial f i ∈ f . Then if the number of complex roots of f is finite, then it is bounded from above by

This bound is a generalization of the fundamental theorem of algebra. Nevertheless, in many cases this bound is rather loose. We can have tighter bounds taking advantage of the particular structure of a polynomial system.

First let us define multihomogeneous polynomial systems that are the basis for the com putation of the mBézout bound.

Definition 6 (Multihomogeneous polynomial)

Let X 1 = (x 1,1 , . . . , x 1,d 1 ), X 2 = (x 2,1 , . . . , x 2,d 2 ), . . . , X n = (x n,1 , . . . , x n,dn ) be a partition of the affine variables x, with

Consider that every f i is homogeneous in each variable set X j , with homogenizing variable x i,0 and multidegree specified by vector α i = (α i,1 , α i,2 , . . . , α i,n ), where α i,j denotes the degree of f i in X j . Then f is multihomogeneous of type (m 1 , . . . , m n ; α 1 , . . . , α n ).

Given this definition, the classic theorem from algebraic geometry [START_REF] Shafarevich | Intersection numbers[END_REF] can be used for the computation of the mBézout bound.

bounds the number of roots of f (x) in P m 1 × • • • × P mn , where Y i are new symbolic pa rameters, and P m i is the m i dimensional projective space over C. The bound is tight for generic coefficients of f (x).