Szervusztok! Új év, új fél év, újra kombinatorika szeminárium:
           Február 8., 10:00, Farkas-terem
Azaz régi idő, régi épületben (egyelőre) régi terem. Az előadás:

<P><CENTER>
Csaba Béla: 
<B>Páros jól-szeparálható gráfok beágyazása</B>
</CENTER>

<P>
Legyen H és G két n csúcsú gráf, ahol H a kicsi (kevés élű)
és G a nagy (sok élű). Biztosak lehetünk abban, hogy H részgráfja
G-nek, ha G minimális foka H maximális fokának egy függvénye.
Ha H csúcsszáma kicsi G csúcsszámához képest, az Erdos-Stone-tétel
szerint már nem H maximális foka, hanem a kromatikus száma a
fontos paraméter.

<P>
Bollobás és Komlós egy régi sejtésben azt fogalmazták meg, hogy
ha H és G n csúcsú és H sávszélessége kicsi, akkor elég H kromatikus
számát tudni, hasonlóan az Erdős-Stone-tételhez.
A Bollobás-Komlós-sejtést pár éve bebizonyították, de a témakör
még (szerintem) tartogatott érdekes kérdést. Az előadáson belátjuk,
hogy a kis sávszélesség a sejtésben nem szükségszerű.
H-nak akár n/10 is lehet a sávszélessége, mégis viszonylag könnyen
beágyazható, ha rendelkezik egy másik tulajdonsággal: jól-szeparálható.

<P>
Minden érdeklődőt szeretettel várunk,

<P>
Péter