Erdős–Faber–Lovász-sejtés

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. Így szól:

Az Erdős–Faber–Lovász-sejtés egy példája: egy négy-négy csúcsból álló négy klikkből alakított gráf, melyben bármely két klikk között pontosan egy közös csúcs van, négy színnel kiszínezhető.

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.

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) 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.

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.

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ő.

Egy G gráf interszekciós számán 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. Erdős eredetileg 50 USD-t ajánlott a sejtés igazolásáért, később 500 dollárra emelte a jutalmat.

(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.

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.

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

• Erdős Pál sejtéseinek listája

Jegyzetek

• 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)