Μονάδα:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Ημερομηνία κατάθεσης:
2020-01-03
Συγγραφέας:
Χανιώτης Αριστοτέλης
Στοιχεία επιβλεπόντων καθηγητών:
Αρχοντία Γιαννοπούλου, Επίκουρη Καθηγήτρια, Τμήμα Πληροφορικής, ΕΚΠΑ
Δημήτριος Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής, ΕΚΠΑ
Πρωτότυπος Τίτλος:
Structural and Topological Graph Theory and Well-Quasi-Ordering
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Δομική και Τοπολογική Θεωρία Γραφημάτων και Καλές-Σχεδόν-Διατάξεις
Περίληψη:
Στη σειρά εργασιών Ελασσόνων Γραφημάτων, οι Neil Robertson και Paul Seymour
μεταξύ άλλων σπουδαίων αποτελεσμάτων, απέδειξαν την εικασία του Wagner που σήμερα
είναι γνωστή ως το Θεώρημα των Robertson και Seymour.
Σε κάθε τους βήμα προς την συναγωγή της τελικής απόδειξης
της εικασίας, κάθε ειδική περίπτωση αυτής που αποδείκνυαν ήταν συνέπεια ενός "δομικού θεωρήματος"
το οποίο σε γενικές γραμμές ισχυριζόταν ότι ικανοποιητικά γενικά γραφήματα περιέχουν ως ελάσσονα γραφήματα
ή άλλες δομές που είναι χρήσιμα για την απόδειξη, ή ισοδύναμα, ότι η δομή των
γραφημάτων τα οποία δεν περιέχουν ένα χρήσιμο για την απόδειξη γράφημα ως έλασσον
είναι κατά κάποιο τρόπο περιορισμένη συνάγοντας έτσι και πάλι μια χρήσιμη πληροφορία για την απόδειξη.
Στην παρούσα εργασία, παρουσιάζουμε -σχετικά μικρές- αποδείξεις διαφόρων ειδικών περιπτώσεων του Θεωρήματος των Robertson και Seymour,
αναδεικνύοντας με αυτό τον τρόπο την αλληλεπίδραση της δομικής θεωρίας γραφημάτων με την θεωρία των
καλών-σχεδόν-διατάξεων.
Παρουσιάζουμε ακόμα την ίσως πιο ενδιαφέρουσα ειδική περίπτωση του Θεωρήματος των Robertson και Seymour,
η οποία ισχυρίζεται ότι η εμβαπτισιμότητα
σε κάθε συγκεκριμένη επιφάνεια δύναται να χαρακτηριστεί μέσω της απαγόρευσης πεπερασμένων το πλήθος γραφημάτων
ως ελάσσονα. Το τελευταίο αποτέλεσμα συνάγεται ως ένα αποτέλεσμα της θεωρίας των καλών-σχεδόν-διατάξεων
αναδεικνύοντας με αυτό τον τρόπο την αλληλεπίδρασή της με την τοπολογική θεωρία γραφημάτων. Τέλος, σταχυολογούμε
αποτελέσματα αναφορικά με την καλή-σχεδόν-διάταξη κλάσεων γραφημάτων από άλλες -πέραν της
σχέσης έλασσον- σχέσεις γραφημάτων.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
θεωρία γραφημάτων, ελάσσονα γραφήματα, δομική θεωρία γραφημάτων, τοπολογική θεωρία γραφημάτων, καλές-σχεδόν-διατάξεις
Αρ. σελίδων ευρετηρίου:
8
Αρ. βιβλιογραφικών αναφορών:
125
