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

Pluhár András: Élszeparáció gráfokban

 iCal fájl letöltése
Péntek, 17. Március 2023, 10:00 - 11:30
A 60-as évek végén Rényi vetett fel egy szeparációs problémát,
utak olyan P halmazát kell venni, hogy bármely f, e élekre legyen
olyan p \in P, melyre e \in p de f
ot \in p.

Ilyen persze van, így a kérdés a P méretének a minimuma.
Mi (társak: Balogh József, Csaba Béla, Ryan Martin) egy teljesen
más probléma kapcsán jutottunk el egy hasonló fogalomhoz. Néhány
korlátot adtunk, ill. egy sejtést, mely szerint erős szeparáció
esetén is elég lehet cn út, ahol n a gráf pontszáma, c konstans.

Ez 2016-ban jelent meg, sokáig nem volt visszhangja, majd 2022-ben
a cn\log^*(n) majdnem lineáris korlátot adta S. Letzter. Néhány
hete Bonamy, Botler, Dross, Naia és Skokan pedig a 19n-et érte
el. Főleg a technikákról és az utóbbi eredményről lesz szó.
 
Az előadás a Riesz teremben lesz.

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013