A matematika, azon belül a gráfelmélet és Ramsey-elmélet területén a Choongbum Lee által 2015-ben bebizonyított; Burr–Erdős-sejtés vagy Erdős–Burr-sejtés (tulajdonképpen: Lee-tétel) a ritka gráfok Ramsey-számával kapcsolatos probléma. Az Erdős Pál és Stefan Burr által felvetett kérdés az volt, hogy tetszőleges ritka gráfcsaládot figyelembe véve vajon a gráfok Ramsey-száma a csúcsok számával lineárisan növekszik-e.

Definíciók Egy G irányítatlan gráf degeneráltsága az a minimális p természetes szám, melyre G bármely részgráfjában található legfeljebb p fokszámú csúcs. Egy p degeneráltságú gráfot p-degeneráltnak mondunk. Ekvivalens megfogalmazás szerint egy p-degenerált gráf a p-nél nem nagyobb fokszámú csúcsok ismételt eltávolításával üres gráffá redukálható.

A Ramsey-tételből következik, hogy minden G gráfhoz tartozik egy legkisebb egész szám, avagy a G gráf Ramsey-száma, hogy bármely, legalább méretű teljes gráf csúcsait két színnel kiszínezve a gráf tartalmazni fogja a G egyszínű kópiáját. Például a háromszög Ramsey-száma 6, mert a hat csúcsból álló teljes gráfot kék és piros színnel kiszínezve mindig találni fogunk vagy kék, vagy piros háromszöget.

A sejtés 1973-ban Stefan Burr és Erdős Pál a következőt sejtették meg:

Minden p egész számhoz létezik egy cp konstans, melyre igaz, hogy bármely n csúcsú p-degenerált gráf Ramsey-száma legfeljebb cp n.

Tehát ha egy n csúcsból álló G gráf p-degenerált, akkor a G egyszínű kópiája megtalálható bármely, két színnel színezett cp n csúcsú teljes gráfban.

Ismert eredmények Jóval a sejtés teljes bizonyítása előtt már léteztek részeredmények vele kapcsolatban. igazolta korlátos fokszámú gráfokra; az ő bizonyításuk nagyon magas cp konstanshoz vezetett; a konstanst , majd javította meg. Általánosabban a sejtést igazolták a p-átrendezhető (p-arrangeable) gráfokra, melyek magukban foglalják a Kp felosztását nem tartalmazó gráfokat, a korlátos maximális fokszámú gráfokat és a síkbarajzolható gráfokat.. Bizonyították a sejtést felosztott gráfokra, melyekben (élek úttá felosztása miatt) nem található egymással szomszédos csúcspár, melynek mindkét tagjának fokszáma kettőnél nagyobb lenne.; .

Általános gráfok Ramsey-számáról ismert, hogy felső korlátja egy a lineárisnál csak kissé erősebben növekvő függvény. Specifikusan, megmutatta, hogy létezik olyan cp konstans, amire bármely p-degenerált n-csúcsú G gráfra:

Fordítás

Jegyzetek

. . . . . . .

. .

Kategória:Ramsey-elmélet Kategória:Gráfelméleti tételek Kategória:Erdős Pál