Back to search

National and Kapodistrian University of Athens

Upper Bounds on the number of embeddings of minimally rigid graphs

Abstract

dc:description

Στη θεωρία γραφημάτων (γράφων), ένα άκαμπτο γράφημα είναι ένα γράφημα που έχει πεπερασμένο αριθμό εμβυθίσεων στο \mathbb{R}d, ως προς τις Ευκλείδιες κινήσεις, για δεδομένα μήκη ακμών. Η εμβύθιση γραφήματος στο \mathbb{R}d είναι μια ανάθεση των κορυφών σε σημεία στο \mathbb{R}d, η οποία δημιουργεί ένα σύνολο με μήκη ακμών που αντιστοιχούν στις αποστάσεις μεταξύ των συνδεδεμένων κορυφών. Μια σημαντική κλάση άκαμπτων γραφημάτων είναι η κλάση των ελαχιστικώς άκαμπτων γραφημάτων. Ένα ελαχιστικώς άκαμπτο γράφημα, είναι ένα γράφημα που είναι άκαμπτο και έχει την ιδιότητα ότι η αφαίρεση οποιασδήποτε ακμής του, δίνει ένα γράφημα που δεν είναι άκαμπτο. Ένα σημαντικό ανοιχτό πρόβλημα είναι η εύρεση άνω φραγμάτων στον αριθμό τον εμβυθίσεων στο \mathbb{R}d. Για ένα μεγάλο χρονικό διάστημα, μόνο το άνω φράγμα \mathcal{O}(2d\cdot|V|) ήταν γνωστό στον αριθμό των εμβυθίσεων, που προέρχεται από την άμεση εφαρμογή του θεωρήματος του B\'ezout. Στο [Bartzos et al., 2020], το φράγμα βελτιώθηκε για $d\geq5$, χρησιμοποιώντας τους permanent πίνακες. Πρόσφατα στο [Bartzos et al., 2021], το ασυμπτωτικό άνω φράγμα βελτιώθηκε για κάθε διάσταση. Στην ειδική περίπτωση του $d=2$, το ασυμπτωτικό άνω φράγμα βελτιώθηκε σε \mathcal(3.7764). Είναι γνωστό ότι ο αριθμός των λύσεων ενός τετράγωνου αλγεβρικού συστήματος σχετίζεται με τον αριθμό των εμβυθίσεων. Συγκεκριμένα, ο αριθμός των μιγαδικών λύσεων ενός τέτοιου αλγεβρικού συστήματος επεκτείνει την έννοια των πραγματικών εμβυθίσεων στον μιγαδικό χώρο, επιτρέποντάς μας να φράξουμε τις μιγαδικές λύσεις χρησιμοποιώντας εργαλεία από τη μιγαδική αλγεβρική γεωμετρία. Σε αυτή την διπλωματική, μετρώντας τους outdegree-περιορισμένους προσανατολισμούς ενός γραφήματος που σχετίζονται με τα αλγεβρικά φράγματα [Bartzos et al., 2020], βελτιώνουμε τα υπάρχοντα άνω φράγματα, για την κλάση των ελαχιστικώς άκαμπτων γραφημάτων, στον αριθμό των εμβυθίσεων.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Τζάμος Χαράλαμπος
  • Tzamos Charalambos

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, English, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:2962981

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Τζάμος Χαράλαμπος; Tzamos Charalambos. Upper Bounds on the number of embeddings of minimally rigid graphs. 2021. https://pergamos.lib.uoa.gr/uoa/dl/object/2962981