Εικασία Έρντος-Φάμπερ-Λοβάς

Από testwiki
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
Μια περίπτωση της εικασίας Έρντος-Φάμπερ-Λοβάς: ένα γράφημα που σχηματίζεται από τέσσερις κλίκες τεσσάρων κορυφών η καθεμία, από τις οποίες οποιεσδήποτε δύο τέμνονται σε μία μόνο κορυφή, μπορεί να είναι τετράχρωμο.

Στη θεωρία γράφων, η εικασία Έρντος-Φάμπερ-Λοβάς είναι πρόβλημα σχετικά με το χρωματισμό γράφου, το οποίο πήρε το όνομά του από τους Πολ Έρντος, Βανς Φάμπερ και Λάσλο Λοβάς, οι οποίοι το διατύπωσαν το 1972[1]:

Αν Πρότυπο:Mvar πλήρεις γράφοι, καθένας από τους οποίους έχει ακριβώς Πρότυπο:Mvar κορυφές, έχουν την ιδιότητα ότι κάθε ζεύγος πλήρων γραφημάτων έχει το πολύ μία κοινή κορυφή, τότε η ένωση των γραφημάτων μπορεί να χρωματιστεί κατάλληλα με Πρότυπο:Mvar χρώματα.

Η εικασία για όλες τις επαρκώς μεγάλες τιμές του Πρότυπο:Mvar αποδείχθηκε από τους Ντονγκ Γιάπ Κανγκ, Τομ Κέλι, Ντανιέλα Κουν, Αμπχισέκ Μετούκου και Ντέρικ Όστχους.[2]

Ισοδύναμες διατυπώσεις

Οι Χάνταντ & Ταρντίφ (Πρότυπο:Harvtxt) εισήγαγαν το πρόβλημα με μια ιστορία σχετικά με την κατανομή των θέσεων σε επιτροπές: ας υποθέσουμε ότι, σε ένα πανεπιστημιακό τμήμα, υπάρχουν Πρότυπο:Mvar επιτροπές, καθεμία από τις οποίες αποτελείται από Πρότυπο:Mvar μέλη ΔΕΠ, και ότι όλες οι επιτροπές συνεδριάζουν στην ίδια αίθουσα, η οποία έχει Πρότυπο:Mvar καρέκλες. Ας υποθέσουμε επίσης ότι το πολύ ένα άτομο ανήκει στην τομή οποιωνδήποτε δύο επιτροπών. Είναι δυνατόν να αναθέσουμε τα μέλη των επιτροπών σε καρέκλες με τέτοιο τρόπο ώστε κάθε μέλος να κάθεται στην ίδια καρέκλα για όλες τις διαφορετικές επιτροπές στις οποίες ανήκει; Σε αυτό το μοντέλο του προβλήματος, τα μέλη ΔΕΠ αντιστοιχούν σε κορυφές γραφημάτων, οι επιτροπές αντιστοιχούν σε πλήρη γραφήματα και οι έδρες αντιστοιχούν σε χρώματα κορυφών.

Ένας γραμμικός υπεργράφημα (επίσης γνωστός ως μερικός γραμμικός χώρος) είναι ένα υπεργράφημα με την ιδιότητα ότι κάθε δύο υπερακμές έχουν το πολύ μία κοινή κορυφή. Ένας υπεργράφημα λέγεται ομοιόμορφος αν όλες οι υπερεκτάσεις του έχουν τον ίδιο αριθμό κορυφών μεταξύ τους. Οι n κλίκες μεγέθους Πρότυπο:Mvar στην εικασία Έρντος-Φάμπερ-Λοβάς μπορούν να ερμηνευθούν ως οι υπερεκτάσεις ενός Πρότυπο:Mvar-ομοιόμορφου γραμμικού υπεργραφήματος που έχει τις ίδιες κορυφές με τον υποκείμενο γράφο. Σε αυτή τη γλώσσα, η εικασία Έρντος-Φάμπερ-Λοβάς δηλώνει ότι, δεδομένου οποιουδήποτε Πρότυπο:Mvar-ομοιόμορφου γραμμικού υπεργράφου με Πρότυπο:Mvar υπερεκτάσεις, μπορεί κανείς να χρωματίσει Πρότυπο:Mvar-χρώματα τις κορυφές έτσι ώστε κάθε υπερεκτάσεις να έχουν μία κορυφή κάθε χρώματος.[3]

Ένα απλό υπεργράφημα είναι ένα υπεργράφημα στο οποίο το πολύ μία υπερδιαστολή συνδέει κάθε ζεύγος κορυφών και δεν υπάρχουν υπερδιαστολές μεγέθους το πολύ ενός. Στη διατύπωση του χρωματισμού γραφημάτων της εικασίας Έρντος-Φάμπερ-Λοβάς, είναι ασφαλές να αφαιρεθούν οι κορυφές που ανήκουν σε μία μόνο κλίκα, καθώς ο χρωματισμός τους δεν παρουσιάζει καμία δυσκολία- μόλις γίνει αυτό, το υπεργράφημα που έχει μία κορυφή για κάθε κλίκα και μία υπερένταση για κάθε κορυφή γραφήματος, σχηματίζει έναν απλό υπεργράφημα. Και, το διπλό υπεργράφημα του χρωματισμού κορυφών είναι ο χρωματισμός ακμών. Έτσι, η εικασία Έρντος-Φάμπερ-Λοβάς είναι ισοδύναμη με τη δήλωση ότι κάθε απλό υπεργράφημα με Πρότυπο:Mvar κορυφές έχει χρωματικό δείκτη (αριθμό χρωματισμού ακμών) το πολύ Πρότυπο:Mvar.[4]

Το γράφημα της εικασίας Έρντος-Φάμπερ-Λοβάς μπορεί να αναπαρασταθεί ως γράφημα τομής συνόλων: σε κάθε κορυφή του γραφήματος αντιστοιχεί το σύνολο των κλιμακίων που περιέχουν την εν λόγω κορυφή, και συνδέει οποιεσδήποτε δύο κορυφές με μια ακμή κάθε φορά που τα αντίστοιχα σύνολά τους έχουν μη κενή τομή. Χρησιμοποιώντας αυτή την περιγραφή του γραφήματος, η εικασία μπορεί να διατυπωθεί ως εξής: αν κάποια οικογένεια συνόλων έχει Πρότυπο:Mvar συνολικά στοιχεία, και οποιαδήποτε δύο σύνολα τέμνονται το πολύ σε ένα στοιχείο, τότε το γράφημα τομής των συνόλων μπορεί να είναι Πρότυπο:Mvar-χρωματισμένο.[5]

Ο αριθμός τομής ενός γράφου Πρότυπο:Mvar είναι ο ελάχιστος αριθμός στοιχείων σε μια οικογένεια συνόλων των οποίων ο γράφος τομής είναι ο Πρότυπο:Mvar, ή ισοδύναμα ο ελάχιστος αριθμός κορυφών σε ένα υπεργράφημα του οποίου ο γραμμικός γράφος είναι ο Πρότυπο:Mvar. Οι Κλάιν & Μάργκραφ (Πρότυπο:Harvtxt) ορίζουν τον αριθμό γραμμικής τομής ενός γράφου, ομοίως, ως τον ελάχιστο αριθμό κορυφών σε έναν γραμμικό υπεργράφημα του οποίου ο γραμμικός γράφος είναι ο Πρότυπο:Mvar. Όπως παρατηρούν, η εικασία των Έρντος-Φάμπερ-Λοβάς είναι ισοδύναμη με τη δήλωση ότι ο χρωματικός αριθμός οποιουδήποτε γράφου είναι το πολύ ίσος με τον αριθμό γραμμικής τομής του.

Οι Χάνταντ & Ταρντίφ (Πρότυπο:Harvtxt) παρουσιάζουν μια άλλη ακόμη ισοδύναμη διατύπωση, με όρους της θεωρίας των κλώνων.

Ιστορική αναδρομή, επιμέρους αποτελέσματα και ενδεχόμενη απόδειξη

Ο Πολ Έρντος, ο Βανς Φέιμπερ και ο Λάσλο Λοβάς διατύπωσαν την αθώα εικασία (harmless looking conjecture) σε ένα πάρτι στο Μπόλντερ του Κολοράντο τον Σεπτέμβριο του 1972. Η δυσκολία της συνειδητοποιήθηκε αργά[1]. Ο Πολ Έρντος προσέφερε αρχικά 50 δολάρια ΗΠΑ για την καταφατική απόδειξη της εικασίας και αργότερα αύξησε την αμοιβή σε 500 δολάρια ΗΠΑ. Στην πραγματικότητα, ο Πολ Έρντος θεωρούσε ότι αυτό ήταν ένα από τα τρία πιο αγαπημένα του προβλήματα συνδυαστικής ανάλυσης.[1][6]

Οι Σιανγκ & Λαουλερ (Πρότυπο:Harvtxt) απέδειξαν ότι ο χρωματικός αριθμός του γράφου της εικασίας είναι το πολύ 32k−2, και ο Καν (1992) το βελτίωσε σε Πρότυπο:Math.

Το 2023, σχεδόν 50 χρόνια μετά τη διατύπωση της αρχικής εικασίας,[1] αυτή επιλύθηκε για όλα τα επαρκώς μεγάλα Πρότυπο:Math από τους Ντονγκ Γιάπ Κανγκ, Τομ Κέλι, Ντανιέλα Κουν, Αμπχισέκ Μετούκου και Ντέρικ Όστχους[7]

Σχετικά προβλήματα

Ενδιαφέρον παρουσιάζει επίσης η εξέταση του χρωματικού αριθμού των γραφημάτων που σχηματίζονται ως ένωση Πρότυπο:Mvar κλικών Πρότυπο:Mvar κορυφών η καθεμία, χωρίς να περιορίζεται το μέγεθος των τομών των ζευγών των κλικών. Στην περίπτωση αυτή, ο χρωματικός αριθμός της ένωσής τους είναι το πολύ Πρότυπο:Math, και ορισμένοι γράφοι που σχηματίζονται με αυτόν τον τρόπο απαιτούν τόσα χρώματα.[8]

Μια εκδοχή της εικασίας που χρησιμοποιεί τον κλασματικό χρωματικό αριθμό στη θέση του χρωματικού αριθμού είναι γνωστό ότι είναι αληθής. Δηλαδή, αν ένας γράφος Πρότυπο:Mvar σχηματίζεται ως η ένωση των Πρότυπο:Mvar Πρότυπο:Mvar-κλικών που τέμνονται κατά ζεύγη σε μία το πολύ κορυφή, τότε το Πρότυπο:Mvar μπορεί να είναι Πρότυπο:Mvar-χρωματισμένο.[9]

Στο πλαίσιο του χρωματισμού ακμών απλών υπεργραφημάτων, ο Χίντμαν (Πρότυπο:Harvtxt) ορίζει έναν αριθμό Πρότυπο:Mvar από ένα απλό υπεργράφημα ως τον αριθμό των κορυφών του υπεργραφήματος που ανήκουν σε μια υπερκορυφή τριών ή περισσότερων κορυφών. Δείχνει ότι, για οποιαδήποτε σταθερή τιμή του Πρότυπο:Mvar, ένας πεπερασμένος υπολογισμός αρκεί για να επαληθεύσει ότι η εικασία είναι αληθής για όλα τα απλά υπεργραφήματα με αυτή την τιμή του Πρότυπο:Mvar. Με βάση αυτή την ιδέα, δείχνει ότι η εικασία είναι πράγματι αληθής για όλα τα απλά υπεργραφήματα με Πρότυπο:Math. Στη διατύπωση του χρωματισμού των γραφημάτων που σχηματίζονται από ενώσεις κλικών, το αποτέλεσμα του Χίντμαν δείχνει ότι η εικασία είναι αληθής κάθε φορά που το πολύ δέκα από τις κλίκες περιέχουν μια κορυφή που ανήκει σε τρίες ή περισσότερες κλίκες. Ειδικότερα, ισχύει για Πρότυπο:Math.

Δείτε επίσης

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

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

Παραπομπές

Πρότυπο:Reflist Πρότυπο:Refbegin

Πρότυπο:Refend

Πηγές

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

  1. ↑ 1,0 1,1 1,2 1,3 Πρότυπο:Harvtxt.
  2. ↑ Πρότυπο:Harvtxt; Πρότυπο:Harvtxt; Πρότυπο:Harvtxt
  3. ↑ Πρότυπο:Harvtxt.
  4. ↑ Πρότυπο:Harvtxt. Πρότυπο:Harvtxt describes an equivalent problem in the language of set systems instead of hypergraphs.
  5. ↑ Πρότυπο:Harvtxt.
  6. ↑ Πρότυπο:Harvtxt.
  7. ↑ Πρότυπο:Harvtxt.
  8. ↑ Πρότυπο:Harvtxt; Πρότυπο:Harvtxt.
  9. ↑ Πρότυπο:Harvtxt.
Ανακτήθηκε από «https://el.wiki.beta.math.wmflabs.org/w/index.php?title=Εικασία_Έρντος-Φάμπερ-Λοβάς&oldid=3086»