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

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

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

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

:\textrm{cr}(K_n)=\frac14\biggl\lfloor\frac{n}{2}\biggr\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor.

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

## Ασυμπτωτικά όρια
Μια ασθενέστερη μορφή της εικασίας, που αποδείχθηκε από τον Μ. Σέφερ, δηλώνει ότι κάθε γράφος με χρωματικό αριθμό n διαθέτει αριθμό διασταυρώσεων \Omega(n^4) (χρησιμοποιώντας τον συμβολισμό big Ο), ή ισοδύναμα ότι κάθε γράφος με αριθμό διασταυρώσεων k διαθέτει χρωματικό αριθμό O(k^{1/4}). Οι Άλμπερτσον, Κράνστον & Φοξ () δημοσίευσαν μια απλή απόδειξη αυτών των ορίων, συνδυάζοντας το γεγονός ότι κάθε ελάχιστος n-χρωματικός γράφος έχει ελάχιστο βαθμό τουλάχιστον &nbsp;n-1 (γιατί αλλιώς ο άπληστος χρωματισμός θα χρησιμοποιούσε λιγότερα χρώματα) μαζί με την ανισότητα του αριθμού διασταυρώσεων σύμφωνα με την οποία κάθε γράφος G=(V,E) με |E|/|V|\ge 4 έχει αριθμό διασταυρώσεων \Omega(|E|^3/|V|^2). Χρησιμοποιώντας τον ίδιο συλλογισμό, δείχνουν ότι ένα αντιπαράδειγμα στην εικασία του Άλμπερτσον για τον χρωματικό αριθμό n (αν υπάρχει) πρέπει να έχει λιγότερες από 4n κορυφές.

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

Η εικασία του Άλμπερτσον είναι  αληθής με κενό τρόπο  για n\le 4. Σε αυτές τις περιπτώσεις, το K_n έχει αριθμό διασταυρώσεων μηδέν, οπότε η εικασία δηλώνει μόνο ότι τα n-χρωματικά γραφήματα έχουν αριθμό διασταυρώσεων μεγαλύτερο ή ίσο του μηδενός, κάτι που ισχύει για όλα τα γραφήματα. Η περίπτωση n=5 της εικασίας του Άλμπερτσον είναι ισοδύναμη με το θεώρημα των τεσσάρων χρωμάτων, ότι δηλαδή κάθε επίπεδο γράφημα μπορεί να χρωματιστεί με τέσσερα ή λιγότερα χρώματα, διότι τα μόνα γραφήματα που απαιτούν λιγότερες διασταυρώσεις από τη μία διασταύρωση του K_5 είναι τα επίπεδα γραφήματα, και η εικασία συνεπάγεται ότι όλα αυτά θα πρέπει να είναι το πολύ 4-χρωματικά. Μέσω των προσπαθειών διαφόρων ομάδων συγγραφέων είναι πλέον γνωστό ότι η εικασία ισχύει για όλα τα n\le 18  Για κάθε ακέραιο αριθμό c\ge 6, οι Λουίζ και Ρίχτερ παρουσίασαν μια οικογένεια (c+1)-χρωματικά κρίσιμων γραφημάτων που δεν περιέχουν υποδιαίρεση του πλήρους γράφου K_{c+1} αλλά έχουν αριθμό διασταύρωσης τουλάχιστον ίσο με αυτόν του K_{c+1}.

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

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

## Εξωτερικοί σύνδεσμοι
*English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
*Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
* Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
* Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
* Θεωρία Αριθμών και Εφαρμογές
* Υπολογιστική Θεωρία Αριθμών

## Δείτε επίσης
* Θεωρία αριθμών
* Αλγεβρική θεωρία αριθμών
* Συζυγής μιγαδικός αριθμός
* Αλγεβρική θεωρία αριθμών
* Ελλειπτική καμπύλη
* e (μαθηματική σταθερά)
* Πυθαγόρεια τετράδα
* Άρτιοι και περιττοί αριθμοί
* Τετραγωνικός αριθμός
* Κρυπτογραφία ελλειπτικών καμπυλών
* Προβλήματα του Λαντάου
* Εικασία του Κράμερ
* Εικασία του Γκόλντμπαχ
* Θεμελιώδες θεώρημα αριθμητικής
* Αλγεβρική γεωμετρία
* Υπόθεση H του Σίνζελ
* Θεώρημα των τεσσάρων χρωμάτων
* Ευκλείδειος χώρος

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

## Παραπομπές

*
*.
*.
*.
*.
*. As cited by .
*.
*.

## Πηγές
* 
* 
* 
* 
* 
* 
* 

Κατηγορία:Διοφαντικές εξισώσεις
Κατηγορία:Περιοχές των μαθηματικών
Κατηγορία:Θεωρία γράφων
Κατηγορία:Θεωρία αριθμών
Κατηγορία:Εικασίες
Κατηγορία:Άλυτα προβλήματα στα μαθηματικά