Εικασία του Άλμπερτσον

Από testwiki
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
Ο πλήρης γράφος K6 που σχεδιάστηκε με τρεις διασταυρώσεις, ο μικρότερος αριθμός διασταυρώσεων οποιουδήποτε γραφήματος που απαιτεί έξι χρώματα

Στη συνδυαστική των μαθηματικών, η εικασία του Άλμπερτσον είναι μια αναπόδεικτη σχέση μεταξύ του αριθμού διασταυρώσεων και του χρωματικού αριθμού ενός γραφήματος. Πήρε το όνομά της από τον Μάικλ Ο. Άλμπερτσον, καθηγητή στο Κολέγιο Σμιθ, ο οποίος τη διατύπωσε ως εικασία το 2007[1] και είναι μία από τις πολλές εικασίες του στη θεωρία χρωματισμού γραφημάτων[2]. Η εικασία δηλώνει ότι, μεταξύ όλων των γραφημάτων που απαιτούν n χρώματα, ο πλήρης γράφος Kn είναι αυτός με τον μικρότερο αριθμό διασταύρωσης. Ισοδύναμα, αν ένας γράφος μπορεί να σχεδιαστεί με λιγότερες διασταυρώσεις από τον Kn τότε, σύμφωνα με την εικασία, μπορεί να χρωματιστεί με λιγότερα από n χρώματα.

Ένας εικαστικός τύπος για τον ελάχιστο αριθμό διασταυρώσεων

Είναι απλό να δείξουμε ότι οι γράφοι με περιορισμένο αριθμό διασταυρώσεων[3] έχουν περιορισμένο χρωματικό αριθμό: μπορούμε να αναθέσουμε διαφορετικά χρώματα στα τελικά σημεία όλων των διασταυρούμενων ακμών και στη συνέχεια να χρωματίσουμε με 4 χρώματα τον υπόλοιπο επιπεδικό γράφημα. Η εικασία του Άλμπερτσον αντικαθιστά αυτή την ποιοτική σχέση μεταξύ του αριθμού διασταυρώσεων[3] και του χρωματισμού με μια ακριβέστερη ποσοτική σχέση. Συγκεκριμένα, μια διαφορετική εικασία του Ρίτσαρντ Κ. Γκι (Πρότυπο:Harvs) δηλώνει ότι ο αριθμός διασταύρωσης του πλήρους γράφουKn είναι

cr(Kn)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋.

Είναι γνωστό πώς να σχεδιάζουμε πλήρεις γράφους με τόσες διασταυρώσεις, τοποθετώντας τις κορυφές σε δύο ομόκεντρους κύκλους- αυτό που δεν γνωρίζουμε είναι αν υπάρχει καλύτερη σχεδίαση με λιγότερες διασταυρώσεις. Επομένως, μια ενισχυμένη διατύπωση της εικασίας Άλμπερτσον είναι ότι κάθε n-χρωματικό γράφημα έχει αριθμό διασταυρώσεων τουλάχιστον τόσο μεγάλο όσο το δεξί μέρος αυτού του τύπου.[4] Αυτή η ενισχυμένη εικασία θα είναι αληθής εάν και μόνο εάν και η εικασία του Γκι και η εικασία του Άλμπερτσον είναι αληθείς.

Ασυμπτωτικά όρια

Μια ασθενέστερη μορφή της εικασίας, που αποδείχθηκε από τον Μ. Σέφερ,[4] δηλώνει ότι κάθε γράφος με χρωματικό αριθμό n διαθέτει αριθμό διασταυρώσεων Ω(n4) (χρησιμοποιώντας τον συμβολισμό big Ο), ή ισοδύναμα ότι κάθε γράφος με αριθμό διασταυρώσεων k διαθέτει χρωματικό αριθμό O(k1/4). Οι Άλμπερτσον, Κράνστον & Φοξ (Πρότυπο:Harvtxt) δημοσίευσαν μια απλή απόδειξη αυτών των ορίων, συνδυάζοντας το γεγονός ότι κάθε ελάχιστος n-χρωματικός γράφος έχει ελάχιστο βαθμό τουλάχιστον  n−1 (γιατί αλλιώς ο άπληστος χρωματισμός θα χρησιμοποιούσε λιγότερα χρώματα) μαζί με την ανισότητα του αριθμού διασταυρώσεων[3] σύμφωνα με την οποία κάθε γράφος G=(V,E) με |E|/|V|≥4 έχει αριθμό διασταυρώσεων Ω(|E|3/|V|2). Χρησιμοποιώντας τον ίδιο συλλογισμό, δείχνουν ότι ένα αντιπαράδειγμα στην εικασία του Άλμπερτσον για τον χρωματικό αριθμό n (αν υπάρχει) πρέπει να έχει λιγότερες από 4n κορυφές.

Ειδικές περιπτώσεις

Η εικασία του Άλμπερτσον είναι αληθής με κενό τρόπο για n≤4. Σε αυτές τις περιπτώσεις, το Kn έχει αριθμό διασταυρώσεων μηδέν, οπότε η εικασία δηλώνει μόνο ότι τα n-χρωματικά γραφήματα έχουν αριθμό διασταυρώσεων μεγαλύτερο ή ίσο του μηδενός, κάτι που ισχύει για όλα τα γραφήματα. Η περίπτωση n=5 της εικασίας του Άλμπερτσον είναι ισοδύναμη με το θεώρημα των τεσσάρων χρωμάτων, ότι δηλαδή κάθε επίπεδο γράφημα μπορεί να χρωματιστεί με τέσσερα ή λιγότερα χρώματα, διότι τα μόνα γραφήματα που απαιτούν λιγότερες διασταυρώσεις από τη μία διασταύρωση του K5 είναι τα επίπεδα γραφήματα, και η εικασία συνεπάγεται ότι όλα αυτά θα πρέπει να είναι το πολύ 4-χρωματικά. Μέσω των προσπαθειών διαφόρων ομάδων συγγραφέων είναι πλέον γνωστό ότι η εικασία ισχύει για όλα τα n≤18 [5] Για κάθε ακέραιο αριθμό c≥6, οι Λουίζ και Ρίχτερ παρουσίασαν μια οικογένεια (c+1)-χρωματικά κρίσιμων γραφημάτων που δεν περιέχουν υποδιαίρεση του πλήρους γράφου Kc+1 αλλά έχουν αριθμό διασταύρωσης τουλάχιστον ίσο με αυτόν του Kc+1.[6]

Σχετικές εικασίες

Υπάρχει επίσης σύνδεση με την εικασία του Χαντβίγκερ, ένα σημαντικό ανοιχτό πρόβλημα της συνδυαστικής που αφορά τη σχέση μεταξύ του χρωματικού αριθμού και της ύπαρξης μεγάλων κλικών ως ελάσσονες σε ένα γράφημα.[7] Μια παραλλαγή της εικασίας του Χαντβίγκερ, που διατυπώθηκε από τον Γκιόργκυ Χάικος, είναι ότι κάθε n-χρωματικός γράφος περιέχει μια υποδιαίρεση του Kn - αν αυτό ήταν αληθές, θα ακολουθούσε η εικασία του Άλμπερτσον, επειδή ο αριθμός διασταυρώσεων ολόκληρου του γράφου είναι τουλάχιστον τόσο μεγάλος όσο ο αριθμός διασταυρώσεων[3] οποιασδήποτε υποδιαίρεσής του. Ωστόσο, τα αντιπαραδείγματα της εικασίας Χατζός είναι πλέον γνωστά[8] οπότε αυτή η σύνδεση δεν παρέχει μια οδό για την απόδειξη της εικασίας Άλμπερτσον.

Εξωτερικοί σύνδεσμοι

Δείτε επίσης

Βιβλιογραφία

Παραπομπές

Πρότυπο:Reflist

Πηγές

Πρότυπο:Portal bar Πρότυπο:Authority control

  1. ↑ According to Πρότυπο:Harvtxt, the conjecture was made by Albertson at a special session of the American Mathematical Society in Chicago, held in October 2007.
  2. ↑ Πρότυπο:Citation.
  3. ↑ 3,0 3,1 3,2 3,3 Πρότυπο:Cite web
  4. ↑ 4,0 4,1 Πρότυπο:Harvtxt.
  5. ↑ Πρότυπο:Harvtxt; Πρότυπο:Harvtxt; Πρότυπο:Harvtxt; Πρότυπο:Harvtxt.
  6. ↑ Πρότυπο:Harvtxt.
  7. ↑ Πρότυπο:Harvtxt.
  8. ↑ Πρότυπο:Harvtxt; Πρότυπο:Harvtxt.
Ανακτήθηκε από «https://el.wiki.beta.math.wmflabs.org/w/index.php?title=Εικασία_του_Άλμπερτσον&oldid=3087»