Év szerint Hónap szerint Ugrás a hónaphoz

Csaba Béla: Páros gráfok pakolása

 iCal fájl letöltése
Péntek, 6. Március 2026, 10:00 - 11:00
Legyen G_1, G_2 két gráf. G_1 parkettázható G_2 példányokkal, ha le tudunk úgy rakni csúcsdiszjunkt G_2-ket G_1-be, hogy ne maradjon ki csúcsa G_1-nek. Majdnem parkettázható, ha egy "kevés", általában konstans sok, néha kis lineáris számú csúcs kimaradhat.

Verstraete 2002-es sejtése úgy szól, hogy ha G egy n csúcsú r-reguláris (minden csúcs foka r) gráf, H egy rögzített gráf, akkor van H-nak olyan TH felosztása (minden élt helyettesítünk egy s>= 2 hosszú úttal, és TH páros legyen), hogy G majdnem parkettázható TH példányokkal, legfeljebb konstans sok maradhat ki.
Pár évvel később Kühn és Osthus belátták a sejtést arra az esetre, ha r=cn valamely c>0 konstansra, illetve approximációt adtak arra az esetre, ha TH helyett H-val parkettázunk, ahol H páros.

Az utóbbi időben (2025-ben és 2026-ban) megjelent pár cikk, amik igen közel kerültek a sejtésnek, vagy valamely változatának a  megoldásához. Montgomery,  Petrova, Ranganathan és Tan belátták a  sejtés egy approximációs változatát, ha r egy elég nagy konstans. Letzter, Methuku és Sudakov bebizonyították, hogy H példányokkal majdnem parkettázható G, csak konstans sok csúcs marad ki, ha r=cn valamely c>0 számra. Azt is belátták, hogy ha r=polylog(n), H rőgzített, akkor TH példányokkal majdnem parkettázható G, csak o(n) csúcs marad fedetlen G-ben.

Ezekről a tételekről és egy ezeket kiegészítő friss eredményemről szeretnék beszélni.

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013