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

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

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

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

Jegyzetek

1. (Erdős 1981).
2. (Kalai 2021); (Kang et al. 2021)
3. A „lineáris tér” itt nem vektortér értelemben értendő
4. (Romero & Sánchez Arroyo 2007).
5. (Chiang & Lawler 1988). (Hindman 1981) ezzel ekvivalens problémát fogalmaz meg a halmazcsaládok nyelvén a hipergráfok helyett.
6. (Hindman 1981).
7. (Chung & Graham 1998).
8. (Erdős 1991); (Horák & Tuza 1990).
9. (Kahn & Seymour 1992).

• .
• .
• .
• . Solutions by Ilias Kastanas, Charles Vanden Eynden, and Richard Holzsager, American Mathematical Monthly 100 (7): 692–693, 1992.
• Archiválva 2011. július 6-i dátummal a Wayback Machine-ben.
• .
• . Corrected in JCTB 51 (2): 329, 1991, to add Tuza's name as coauthor.
• .
• .
• .
• .

További információk

• Gócza Gergely: Erdős, Faber és Lovász sejtéséről (szakdolgozat, 2015)