Előző hónap Előző nap Következő nap Következő hónap
Év szerint Hónap szerint Ugrás a hónaphoz

Biro Csaba (University of Louisville): Részbenrendezett halmazok dimenziója és a diagramjuk kapcsolata

iCal fájl letöltése
Szerda, 26. Június 2013, 10:00 - 11:30

Tekintsük egy P részbenrendezett halmaz lineáris kiterjesztéseinek egy összességét. Ezt realizátornak nevezzük, ha ezek metszete (mint relációk) egyenlő P-vel. Egy minimális számosságú realizátor számossága a P dimenziója. Részbenrendezett halmazok dimenzióját regóta használják azok komplexitásának mérésére. Így kézenfekvő azt feltételezni, hogy ha egy részbenrendezett halmaz Hasse diagramja valamilyen szempontból egyszerű, (például síkba rajzolható), akkor dimenziója kicsi. Erre sajnos vannak ismert ellenpéldák, de ennek ellenére nem reménytelen egyéb kapcsolatok után kutatni.

Nemrégiben Joret et al. bebizonyították, hogy a dimenzió felülről korlátozható a diagram faszélessége és a magasság függvényével. Az ő korlátjuk óriási (dupla exponenciális), és legérzékenyebb a magasságra. Feltették azonban azt a kérdést, hogy ha a diagram útszélessége legfeljebb kettő (és a magasság nem korlátozott), igaz-e, hogy a dimenzió korlátos. Ezt a kérést igenlően megválaszoljuk. Az előadásban elhangzik a bizonyítás és néhány további nyitott kérdés.

A fent említett cikk társszerzői Mitchel T. Keller és Stephen J. Young.

Hely : Kossuth Lajos sgt. 42., F17 folyóiratolvasó

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013