Bounds on the maximal number of graph embeddings

Abstract

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 $\mathbb{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 $\RR^d$ used to be $O\left(2^{d \cdot |V|}\right)$, while for the cases of $d=2$ and $d=3$ it has been proved that there are graphs with $\Omega\left(2.3003^{|V|}\right)$ and $\Omega\left(2.5198^{|V|}\right)$ 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 (m-Bézout) bound of well-constrained algebraic systems. The first one relates the m-Bézout bound with the number of certain oudegree-constrained graph orientations, while the second uses matrix permanent formulation. Then, we examine the exactness of these bounds on the number of complex embeddings.First with computations indicating that the m-Bé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 m-Bézout bound by analyzing the associated Newton Polytopes. Using these two methods, we improve the upper bounds on the number of graph embeddings. A first improvement is achieved for realizations of graphs in $d\geq 5$ and planar graphs in $\CC^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\left(3.7764^{|V|}\right)$ and $O\left(6.8399^{|V|}\right)$ 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 7-vertex graphs in $\RR^2$ and $\RR^3$, while for the previously untreated case of $S^2$ we give a full characterization for all 6-vertex graphs. We also establish new asymptotic lower bounds on the maximal number of realizations (or simply \emph{lower bounds}) proving that in $\RR^2, S^2$ and $\RR^3$ there exist graphs with $\Omega\left(2.3780^{|V|}\right)$, $\Omega\left(2.5198^{|V|}\right)$ and $\Omega\left(2.6553^{|V|}\right)$ embeddings respectively.

Η Θεωρία Άκαμπτων Γράφων (Θ.Α.Γ.) είναι ο κλάδος των μαθηματικών που μελετά τις εμβυθίσεις γράφων (ή διαμορφώσεις) σε έναν ευκλείδιο χώρο ή μια πολλαπλότητα. Εφόσον ο αριθμός των εμβυθίσεων ως προς τις ευκλείδιες κινήσεις είναι πεπερασμένος για δεδομένα βάρη των ακμών του γράφου, που αντιστοιχούν σε αποστάσεις, τότε ο γράφος ονομάζεται άκαμπτος, αλλιώς ονομάζεται έυκαμπτος. Ο υπολογισμός του αριθμού αυτού μπορεί να γίνει συνδέοντας τις αποστάσεις μεταξύ κορυφών που βρίσκονται σε μία ακμή με αλγεβρικά συστήματα. Ως εκ τούτου ο αριθμός των πραγματικών ριζών αυτών των συστημάτων αντιστοιχεί στον αριθμό των διαμορφώσεων. Οι μιγαδικές ρίζες αυτών των συστημάτων επεκτείνουν την έννοια των άκαμπτων γράφων στους μιγαδικούς ευκλείδιους χώρους και τις αντίστοιχες πολλαπλότητες. Ένα από τα βασικά ερωτήματα στην Θ.Α.Γ. είναι η αναζήτηση άνω φραγμάτων στον αριθμό των εμβυθίσεων για έναν δοσμένο αριθμό κορυφών που να μπορούν να πραγματωθούν. Το μέχρι τώρα γνωστό άνω φράγμα για κάθε ευκλείδιο χώρο διάστασης $d$ για έναν άκαμπτο γράφο $G(V,E)$ ήταν της τάξης του $O(2^{d\cdot|V|})$, ενώ το μέγιστο των εμβυθίσεων που έχουν βρεθεί για συγκεκριμένους γράφους είναι της τάξης του $Ω(2.3003^{|V|})$ στο επίπεδο και $Ω(2.5198^{|V|})$ στον χώρο. Σε αυτή την διατριβή, αναπτύσσονται μέθοδοι που μειώνουν το κενό αυτό μεταξύ των άνω φραγμάτων και των (υπολογισμένων) κάτω φραγμάτων του μεγίστου αριθμού των εμβυθίσεων.Για αυτόν τον σκοπό, προτείνουμε δύο μεθόδους για τον υπολογισμό του πολυ-ομογενούς φράγματος Bézout (Π.Φ. Bézout) τετράγωνων αλγεβρικών συστημάτων. Αρχικά, συνδέουμε το φράγμα αυτό με τον αριθμό διαφορετικών προσανατολισμένων γράφων που μπορεί να προκύψει με βάση περιορισμούς στο βαθμό εξερχόμενων ακμών κάθε κορυφής ενός αρχικά μη προσανατολισμένου γράφου. Επιπλέον, χρησιμοποιούμε την permanent πινάκων που σχετίζονται με το αλγεβρικό σύστημα. Στην συνέχεια μελετάμε την ακρίβεια αυτού του φράγματος σε σχέση με τον αριθμό εμβυθίσεων σε μιγαδικούς χώρους. Βρίσκουμε ότι ο υπολογισμός του όριου για μια πλειάδα γράφων υποδεικνύει ότι για συγκεκριμένες κλάσεις αυτό μπορεί να είναι ακριβές. Αυτό μας παρακινεί να χρησιμοποιήσουμε το δεύτερο θεώρημα του Bernstein, που αφορά την ακρίβεια των μεικτών όγκων, και να αναλύσουμε τις συνθήκες των πολυτόπων του Newton οι οποίες καθιστούν το φράγμα μας ακριβές. Το επόμενο βήμα είναι η βελτίωση των ασυμπτωτικών άνω φραγμάτων. Εφαρμόζοντας άμεσα υπάρχοντα φράγματα των permanent και των προσανατολισμών επίπεδων γραφημάτων, βρίσκουμε μια πρώτη βελτίωση σε συγκεκριμένες κατηγορίες άκαμπτων γράφων, δηλαδή αυτών που εμβυθίζονται σε μεγάλες διαστάσεις ($d\geq5$), καθώς και επίπεδων γράφων που εμβυθίζονται στον χώρο.Έπειτα, αναπτύσσουμε μια μέθοδο που συνδέει τα άνω φράγματα στους προσανατολισμούς των γράφων με μια διαδικασία σταδιακής απαλοιφής κορυφών. Αυτή η μέθοδος μειώνει τα άνω φράγματα σε όλες τις κατηγορίες των γράφων που εξετάζουμε, σπάζοντας για πρώτη φορά τα τετριμμένα φράγματα για τις εμβυθίσεις στο επίπεδο και το χώρο, αποδεικνείοντας ότι είναι της τάξης του $O(3.7764^{|V|})$ και $O(6.8399^{|V|})$ αντίστοιχα. Το τελευταίο πρόβλημα που μας απασχολεί είναι η εύρεση κάτω φραγμάτων του μεγίστου αριθμού των εμβυθίσεων συγκεκριμένων γράφων. Αυτό επιτυγχάνεται με την αναζήτηση των αποστάσεων που ταυτίζουν των αριθμό των πραγματικών λύσεων των αλγεβρικών συστημάτων με αυτό των μιγαδικών. Τα αποτελέσματά μας ταξινομούν πλήρως ως προς τον μέγιστο αριθμό διαμορφώσεων όλους τους άκαμπτους γράφους με $7$ κορυφές που εμβυθίζονται στο επίπεδο και τον χώρο, καθώς και τους γράφους με $6$ κορυφές που εμβυθίζονται στην σφαίρα $S^2$.Επιπλέον βελτιώνουν τα υπάρχοντά κάτω φράγματα του μέγιστου αριθμού διαμορφώσεων σε $Ω(2.3780^{|V|})$ στο επίπεδο, $Ω(2.5198^{|V|})$ στην σφαίρα $S^2$ και $Ω(2.6553^{|V|})$ στον χώρο.