Διασπάσεις εντός κλάσεων κλειστών υπό ελάσσονα προς γραφήματα χαμηλού μέγιστου βαθμού

Submitted by admin on Wed, 03/09/2025 - 08:52
Όνομα
Ορέστης Κ. Μηλολιδάκης
Ημερομηνία παρουσίασης
21-03-2025
Τριμελής επιτροπή
Δημήτρης Αχλιόπτας
Άγγελος Γεωργακόπουλος (Συνεπιβλέπων)
Αρχοντία Γιαννοπούλου
Άρης Παγουρτζής (Συνεπιβλέπων)
Σύνοψη

Είναι εύκολο να δει κανείς ότι κάθε επίπεδο γράφημα είναι έλασσον ενός επιπέδου γραφήματος μέγιστου βαθμού 3. Ο Γεωργακόπουλος απέδειξε ότι κάθε γράφημα που εξαιρεί το K5 ως έλασσον είναι έλασσον ενός άλλου γραφήματος που εξαιρεί το K5 ως έλασσον μέγιστου βαθμού 22, και ρώτησε αν αυτός είναι ο ελάχιστος δυνατόν. Αυτό παρακινεί την εξής γενίκευση. Έστω 𝐶 μία κλάση κλειστή υπό ελάσσονα. Ποιο είναι το ελάχιστο 𝑘 έτσι ώστε οποιοδήποτε γράφημα της 𝐶 είναι έλασον ενός γραφήματος της 𝐶 μέγιστου βαθμού 𝑘; Συμβολίζουμε το ελάχιστο με Δ(𝐶) και θέτουμε την τιμή του σε ∞ εάν δεν υπάρχει τέτοιο 𝑘.

Εξερευνούμε την τιμή του Δ(𝐶) για ποικίλες κλάσεις κλειστές υπό ελάσσονα και τελικά αποδεικνύουμε ότι μια κλάση κλειστή υπό ελάσσονα 𝐶 αποκλείει ένα απόγειο γράφημα ως έλασσον εάν και μόνο εάν υπάρχει μια κλειστή υπό ελάσσονα υπερκλάση 𝐶′ της 𝐶 με Δ(𝐶′) = 3 εάν και μόνο εάν υπ άρχει κλειστή υπό ελάσσονα υπερκλάση 𝐶′ με πεπερασμένο Δ(𝐶′). Αυτό επαυξάνει μια λίστα με 5 άλλους χαρακτηρισμούς των κλάσεων κλειστών υπό ελάσσονα που αποκλείουν ένα απόγειο γράφημα από τους Dujmovic, Morin και Wood. Επιπλέον, επεκτείνουμε και απλοποιούμε το αποτέλεσμα των Markov και Shi ότι δεν έχει κάθε γράφημα δενδροπλάτους ≤ k διάσπαση μέγιστου βαθμού 3 και δενδροπλάτους ≤ 𝑘.

Τέλος, απλοποιούμε την απόδειξη του Γεωργακόπουλου για την ύπαρξη ενός αριθμίσιμα άπειρου καθολικού γραφήματος για την 𝐹 𝑜𝑟𝑏(𝐾5).