Erdős–Faber–Lovász-sejtés
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture.svg/260px-Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture.svg.png)
A gráfelmélet területén az Erdős–Faber–Lovász-sejtés a gráfok színezésének egy megoldatlan problémája, amit Erdős Pálról, Vance Faberről és Lovász Lászlóról neveztek el, akik 1972-ben megfogalmazták.[1] Így szól:
- Vegyünk k teljes gráfot, melyek mindegyikének pontosan k csúcspontja van, és bármely két gráfnak pontosan egy közös csúcsa van, akkor a gráfok egyesítésével kapott gráf k színnel színezhető.
A sejtés egy bizonyítását k elegendően nagy értékeire 2021-ben jelentették be Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku és Deryk Osthus.[2]
Egyenértékű megfogalmazások
(Haddad & Tardif 2004) fogalmazta meg a bizottságok ülésrendjének problémáját: tegyük fel, hogy egy egyetemi tanszéken k bizottság létezik, mindegyiknek k tagja van, és minden bizottság ugyanabban a szobában ülésezik, melyben k szék található. Itt is tételezzük fel, hogy bármely két bizottság metszetében legfeljebb egy ember található. Lehetséges-e a bizottsági tagok leültetése olyan módon, hogy minden tag ugyanabban a székben maradhasson, bármelyik bizottság ülésezik is éppen? Ebben a megközelítésben a bizottsági tagok a gráfok csúcspontjainak felelnek meg, a bizottságok a teljes gráfoknak, a székek pedig a csúcsok színezéseinek.
Egy lineáris hipergráf (más néven részleges lineáris tér[3]) olyan hipergráf, melyben bármely két hiperél között legfeljebb egy közös csúcs van. Egy hipergráf akkor uniform, ha minden hiperéle ugyanannyi csúcsot köt össze. Az Erdős–Faber–Lovász-sejtés n méretű n klikkje úgy is értelmezhető, mint hiperélek egy n-uniform lineáris hipergráfban, melynek ugyanannyi csúcspontja van, mint a kiindulási gráf. Ilyen megközelítésben az Erdős–Faber–Lovász-sejtés azt mondja ki, hogy bármely n-uniform, n hiperéllel rendelkező lineáris hipergráfhoz tartozik olyan színezés, hogy n színnel ki lehet úgy színezni a csúcsokat, hogy minden hiperél mindegyik színű csúcsból éppen egyet tartalmazzon.[4]
Az egyszerű hipergráf (az egyszerű gráf mintájára) olyan hipergráf, melyben egyik hiperél sem tartalmazza a másikat (két csúcsot legfeljebb egy hiperél köt össze). Az Erdős–Faber–Lovász-sejtés gráfszínezési részében nyugodtan el lehet távolítani azokat a csúcsokat, amik egyetlen klikkhez tartoznak, hiszen a színezésük nem okoz problémát; ha ez megvan, a hipergráf minden klikkhez pontosan egy csúcsot és minden csúcshoz pontosan egy hiperélt tartalmaz, így alkotva egyszerű hipergráfot. A csúcsszínezés hipergráf-duálisa az élszínezés. Tehát az Erdős–Faber–Lovász-sejtés ekvivalens azzal az állítással, hogy bármely egyszerű n csúcsú hipergráf kromatikus indexe (élkromatikus száma) legfeljebb n.[5]
Az Erdős–Faber–Lovász-sejtés gráfja kifejezhető továbbá halmazok metszetgráfjaként: a gráf minden csúcsa megfelel a csúcsot tartalmazó klikkek halmaza, és két csúcs akkor van éllel összekötve, ha a megfelelő halmazok metszete nem üres. Ezt a leírást használva a sejtés így fogalmazható meg: ha valamely halmazcsalád összesen n elemű, és bármely két halmaz metszete legfeljebb egy elemet tartalmaz, akkor a halmazok metszetgráfja n-színezhető.[6]
Egy G gráf interszekciós számán(wd) az olyan halmazcsaládok minimális elemszámát értjük, melyek metszetgráfja G, vagy ami ezzel ekvivalens, az G élgráfú hipergráf minimális csúcsainak számát. (Klein & Margraf 2003) meghatározza egy gráf lineáris interszekciós számát; hasonlóan, hogy az a G élgráfú lineáris hipergráf minimális csúcsszáma legyen. Megfigyelésük szerint az Erdős–Faber–Lovász-sejtés ekvivalens azzal az állítással, hogy bármely gráf kromatikus száma kisebb vagy egyenlő, mint a lineáris interszekciós száma.
(Haddad & Tardif 2004) a klónok (speciális művelethalmazok) elméletén belül alkotott ekvivalens megfogalmazást.
Történet, részeredmények
Erdős Pál, Vance Faber és Lovász László fogalmazta meg 1972-ben a sejtést.[1] Erdős eredetileg 50 USD-t ajánlott a sejtés igazolásáért, később 500 dollárra emelte a jutalmat.[1][7]
(Chiang & Lawler 1988) igazolta, hogy a sejtésben szereplő gráfok kromatikus száma legfeljebb 3k/2 − 2, (Kahn 1992) ezt javította k + o(k)-ra.
Kapcsolódó problémák
Érdekes lehet a k csúcsú k db klikkből összeállított gráfok kromatikus számát megvizsgálni, anélkül is, hogy kikötnénk a klikkek közötti páronkénti metszetek számát. Ebben az esetben az uniógráf kromatikus száma legfeljebb 1 + k √k − 1, és léteznek olyan gráfok, amikhez szükség is van éppen ennyi színre.[8]
A sejtés egy változatát, amit egész helyett frakcionális kromatikus számot használ kromatikus számok helyett már sikerült igazolni.[9]
Az egyszerű hipergráfok élszínezésének kontextusában (Hindman 1981) definiálja az egyszerű hipergráfhoz tartozó L számot, mint az olyan hipergráf-csúcsok számát, ami három vagy több csúcson átmenő hiperélhez tartozik. Megmutatja, hogy bármely fix L értékhez véges számításmennyiséggel meghatározható, hogy az összes, adott L értékű egyszerű hipergráfra igaz-e a sejtés. Az ötlet alapján igazolta is, hogy a sejtés valóban igaz az összes L ≤ 10 egyszerű hipergráfra. Gráfszínezés szempontjából ez azt igazolja, hogy a sejtés igaz olyan gráfokra, melyekben legfeljebb 10 olyan klikk van, aminek az egyik csúcsa 3 vagy több klikkbe tartozik. Ez n ≤ 10-re feltétlen igaz.
Kapcsolódó szócikkek
Jegyzetek
- ↑ a b c (Erdős 1981).
- ↑ (Kalai 2021); (Kang et al. 2021)
- ↑ A „lineáris tér” itt nem vektortér értelemben értendő
- ↑ (Romero & Sánchez Arroyo 2007).
- ↑ (Chiang & Lawler 1988). (Hindman 1981) ezzel ekvivalens problémát fogalmaz meg a halmazcsaládok nyelvén a hipergráfok helyett.
- ↑ (Hindman 1981).
- ↑ (Chung & Graham 1998).
- ↑ (Erdős 1991); (Horák & Tuza 1990).
- ↑ (Kahn & Seymour 1992).
- 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, pp. 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, 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: 545–549, <http://lists.rmc.ca/academic/math_cs/tardif/paper25/paper25.pdf>. Hozzáférés ideje: 2009-04-02 Archiválva 2011. július 6-i dátummal a Wayback Machine-ben.
- Hindman, Neil (1981), "On a conjecture of Erdős, Faber, and Lovász about n-colorings", Canad. 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.
- 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.
- 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
- Kang, Dong Yeap; Kelly, Tom & Kühn, Daniela et al. (2021), A proof of the Erdős-Faber-Lovász conjecture
- 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", in Grimmet, Geoffrey & McDiarmid, Colin, Combinatorics, Complexity, and Chance : A Tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, pp. 285–298, DOI 10.1093/acprof:oso/9780198571278.003.0017.
További információk
- Gócza Gergely: Erdős, Faber és Lovász sejtéséről (szakdolgozat, 2015)