Bounds on the maximal number of graph embeddings
Authors: Μπάρτζος Ευάγγελος 
Published: July 2022

Η Θεωρία Άκαμπτων Γράφων (Θ.Α.Γ.) είναι ο κλάδος των μαθηματικών που μελετά τις εμβυθίσεις γράφων (ή διαμορφώσεις) σε έναν ευκλείδιο χώρο ή μια πολλαπλότητα. Εφόσον ο αριθμός των εμβυθίσεων ως προς τις ευκλείδιες κινήσεις είναι πεπερασμένος για δεδομένα βάρη των ακμών του γράφου, που αντιστοιχούν σε αποστάσεις, τότε ο γράφος ονομάζεται άκαμπτος, αλλιώς ονομάζεται έυκαμπτος. Ο υπολογισμός του αριθμού αυτού μπορεί να γίνει συνδέοντας τις αποστάσεις μεταξύ κορυφών που βρίσκονται σε μία ακμή με αλγεβρικά συστήματα. Ως εκ τούτου ο αριθμός των πραγματικών ριζών αυτών των συστημάτων αντιστοιχεί στον αριθμό των διαμορφώσεων. Οι μιγαδικές ρίζες αυτών των συστημάτων επεκτείνουν την έννοια των άκαμπτων γράφων στους μιγαδικούς ευκλείδιους χώρους και τις αντίστοιχες πολλαπλότητες. Ένα από τα βασικά ερωτήματα στην Θ.Α.Γ. είναι η αναζήτηση άνω φραγμάτων στον αριθμό των εμβυθίσεων για έναν δοσμένο αριθμό κορυφών που να μπορούν να πραγματωθούν. Το μέχρι τώρα γνωστό άνω φράγμα για κάθε ευκλείδιο χώρο διάστασης $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|})$ στον χώρο.