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

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

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

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

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

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

Ένα απλό υπεργράφημα είναι ένα υπεργράφημα στο οποίο το πολύ μία υπερδιαστολή συνδέει κάθε ζεύγος κορυφών και δεν υπάρχουν υπερδιαστολές μεγέθους το πολύ ενός. Στη διατύπωση του χρωματισμού γραφημάτων της εικασίας Έρντος-Φάμπερ-Λοβάς, είναι ασφαλές να αφαιρεθούν οι κορυφές που ανήκουν σε μία μόνο κλίκα, καθώς ο χρωματισμός τους δεν παρουσιάζει καμία δυσκολία- μόλις γίνει αυτό, το υπεργράφημα που έχει μία κορυφή για κάθε κλίκα και μία υπερένταση για κάθε κορυφή γραφήματος, σχηματίζει έναν απλό υπεργράφημα. 
Και, το διπλό υπεργράφημα του χρωματισμού κορυφών είναι ο χρωματισμός ακμών. Έτσι, η εικασία Έρντος-Φάμπερ-Λοβάς είναι ισοδύναμη με τη δήλωση ότι κάθε απλό υπεργράφημα με  κορυφές έχει χρωματικό δείκτη (αριθμό χρωματισμού ακμών) το πολύ ..  describes an equivalent problem in the language of set systems instead of hypergraphs.

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

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

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

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

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

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

 Σχετικά προβλήματα 
Ενδιαφέρον παρουσιάζει επίσης η εξέταση του χρωματικού αριθμού των γραφημάτων που σχηματίζονται ως ένωση  κλικών  κορυφών η καθεμία, χωρίς να περιορίζεται το μέγεθος των τομών των ζευγών των κλικών. Στην περίπτωση αυτή, ο χρωματικός αριθμός της ένωσής τους είναι το πολύ {{math|1+ k{{sqrt|''k - 1}}}}, και ορισμένοι γράφοι που σχηματίζονται με αυτόν τον τρόπο απαιτούν τόσα χρώματα.; .

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

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

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

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

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





 <






 Παραπομπές 

.
.
.
. Solutions by Ilias Kastanas, Charles Vanden Eynden, and Richard Holzsager, :en:American Mathematical Monthly 100''' (7): 692–693, 1992

.
.
. Corrected in JCTB 51 (2): 329, 1991, to add Tuza's name as coauthor.

.
.

.
.

 Πηγές 








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