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

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

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

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

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

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

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

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

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

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

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

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

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

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

Οι Σιανγκ & Λαουλερ (Chiang & Lawler (1988)) απέδειξαν ότι ο χρωματικός αριθμός του γράφου της εικασίας είναι το πολύ ${\tfrac {3}{2}}k-2$, και ο Καν (1992) το βελτίωσε σε k + o(k).

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

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

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

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

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

Δείτε επίσης

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

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

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

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

• Graham, Ronald Lewis· Nesetril, Jaroslav (6 Δεκεμβρίου 2012). The Mathematics of Paul Erdös I. Springer Science & Business Media. ISBN 978-3-642-60408-9. 
• Scheinerman, Edward R.· Ullman, Daniel H. (29 Απριλίου 2013). Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Courier Corporation. ISBN 978-0-486-29213-7. 
• West, Douglas B. (2021). Combinatorial Mathematics. Cambridge University Press. ISBN 978-1-107-05858-3. 
• Beineke, Lowell W.· Wilson, Robin J. (7 Μαΐου 2015). Topics in Chromatic Graph Theory. Cambridge University Press. ISBN 978-1-316-23985-8. 
• Ghosh, Smita· Zhang, Zhao (2024). Algorithmic Aspects in Information and Management: 18th International Conference, AAIM 2024, Virtual Event, September 21–23, 2024, Proceedings, Part II. Springer Nature. ISBN 978-981-97-7801-0. 
• <Dinitz, Jeffrey H.· Stinson, Douglas R. (4 Αυγούστου 1992). Contemporary Design Theory: A Collection of Surveys. John Wiley & Sons. ISBN 978-0-471-53141-8. 
• Graham, Ronald L.· Grötschel, Martin (11 Δεκεμβρίου 1995). Handbook of Combinatorics Volume 1. Elsevier. ISBN 978-0-444-82346-5. 
• Society, Canadian Mathematical (7 Ιουνίου 1981). Canadian Journal of Mathematics. Canadian Mathematical Society. 
• Bárány, Imre· Katona, Gyula O. H. (4 Φεβρουαρίου 2020). Building Bridges II: Mathematics of László Lovász. Springer Nature. ISBN 978-3-662-59204-5. 
• Nešetřil, Jaroslav· Pellegrini, Marco (18 Ιανουαρίου 2014). The Seventh European Conference on Combinatorics, Graph Theory and Applications: EuroComb 2013. Springer Science & Business Media. ISBN 978-88-7642-475-5. 
• Chatterji, S. D. (6 Δεκεμβρίου 2012). Proceedings of the International Congress of Mathematicians: August 3–11, 1994 Zürich, Switzerland. Birkhäuser. ISBN 978-3-0348-9078-6. 

Παραπομπές

• Chiang, W. I.; Lawler, E. L. (1988), «Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász», Combinatorica 8 (3): 293–295, doi:10.1007/BF02126801 .
• Chung, Fan; Graham, Ron (1998), Erdős on Graphs: His Legacy of Unsolved Problems, A K Peters, σελ. 97–99 .
• Erdős, Paul (1981), «On the combinatorial problems which I would most like to see solved», Combinatorica 1: 25–42, doi:10.1007/BF02579174 .
• Erdős, Paul (1991), «Advanced problem 6664», American Mathematical Monthly (Mathematical Association of America) 98 (7): 655, doi:10.2307/2324942 . Solutions by Ilias Kastanas, Charles Vanden Eynden, and Richard Holzsager, en:American Mathematical Monthly 100 (7): 692–693, 1992

• Haddad, L.; Tardif, C. (2004), «A clone-theoretic formulation of the Erdős-Faber-Lovasz conjecture», Discussiones Mathematicae Graph Theory 24 (3): 545–549, doi:10.7151/dmgt.1252 .
• Hindman, Neil (1981), «On a conjecture of Erdős, Faber, and Lovász about n-colorings», Can. J. Math. 33 (3): 563–570, doi:10.4153/CJM-1981-046-9 .
• Horák, P.; Tuza, Z. (1990), «A coloring problem related to the Erdős–Faber–Lovász conjecture», Journal of Combinatorial Theory, Series B 50 (2): 321–322, doi:10.1016/0095-8956(90)90087-G . Corrected in JCTB 51 (2): 329, 1991, to add Tuza's name as coauthor.
• Houston-Edwards, Kelsey (April 5, 2021), «Mathematicians settle Erdős coloring conjecture», Quanta Magazine, https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/ 
• Kahn, Jeff (1992), «Coloring nearly-disjoint hypergraphs with n + o(n) colors», Journal of Combinatorial Theory, Series A 59: 31–39, doi:10.1016/0097-3165(92)90096-D .
• Kahn, Jeff; Seymour, Paul D. (1992), «A fractional version of the Erdős-Faber-Lovász conjecture», Combinatorica 12 (2): 155–160, doi:10.1007/BF01204719 .
• Kahn, Jeff (1997), «On Some Hypergraph Problems of Paul Erdős and the Asymptotics of Matchings, Covers and Colorings», The Mathematics of Paul Erdös I, Algorithms and Combinatorics, 13, Springer Berlin Heidelber, σελ. 345–371, doi:10.1007/978-3-642-60408-9_26, ISBN 978-3-642-60408-9, https://doi.org/10.1007/978-3-642-60408-9_26 
• Kalai, Gil (January 14, 2021), «To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus!», Combinatorics and more, https://gilkalai.wordpress.com/2021/01/14/to-cheer-you-up-in-difficult-times-17-amazing-the-erdos-faber-lovasz-conjecture-for-large-n-was-proved-by-dong-yeap-kang-tom-kelly-daniela-kuhn-abhishek-methuku-and-deryk-osthus/ 
• Kang, Dong Yeap; Kelly, Tom; Kühn, Daniela; Methuku, Abhishek; Osthus, Deryk (2023), «A proof of the Erdős-Faber-Lovász conjecture», Annals of Mathematics 198 (2): 537–618, doi:10.4007/annals.2023.198.2.2 
• Klein, Hauke; Margraf, Marian (2003), On the linear intersection number of graphs .
• Romero, David; Sánchez Arroyo, Abdón (2007), «Advances on the Erdős–Faber–Lovász conjecture», στο: Grimmet, Geoffrey; McDiarmid, Colin, επιμ., Combinatorics, Complexity, and Chance : A Tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, σελ. 285–298, doi:10.1093/acprof:oso/9780198571278.003.0017, ISBN 9780198571278 .

Πηγές

• Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9, https://archive.org/details/introductiontoan00apos_0 
• Conway, John Horton; Guy, Richard K. (1996), The Book of Numbers, New York: Copernicus, ISBN 978-0-387-97993-9 
• Crandall, Richard; Pomerance, Carl (2005), Prime Numbers: A Computational Perspective (2nd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-0-387-25282-7 
• Singer, I. M.· Thorpe, J. A. (28 Μαΐου 2015). Lecture Notes on Elementary Topology and Geometry. Springer. ISBN 978-1-4615-7347-0. 
• Apostol, Tom M. (29 Ιουνίου 2013). Introduction to Analytic Number Theory. Springer Science & Business Media. ISBN 978-1-4757-5579-4. 
• Miller, P. D. (2006), Applied Asymptotic Analysis, American Mathematical Society, ISBN 9780821840788, https://books.google.com/books?id=KQvqBwAAQBAJ 
• Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9, https://archive.org/details/introductiontoan00apos_0