Burr–Erdős-sejtés
A matematika, azon belül a gráfelmélet és Ramsey-elmélet területén a Choongbum Lee által 2015-ben bebizonyított[1] 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. Sablon:Harvtxt igazolta korlátos fokszámú gráfokra; az ő bizonyításuk nagyon magas cp konstanshoz vezetett; a konstanst Sablon:Harvtxt, majd Sablon:Harvtxt 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.[2] 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.[3]
Á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, Sablon:Harvtxt megmutatta, hogy létezik olyan cp konstans, amire bármely p-degenerált n-csúcsú G gráfra: