Description
EGERVÁRY SZEMINÁRIUM
Absztrakt: A diszkrepancia egy adott halmazrendszer összetettségét
méri: hogyan tudjuk az alaphalmaz elemeit két színnel, pirossal és
kékkel színezni úgy, hogy egyik részhalmazban se térjen el egymástól
jelentősen a piros, illetve a kék elemek elemszáma. Előadásomban
röviden ismertetem a diszkrepanciával kapcsolatos alaperedményeket. Az
első nemtriviális felső korlát Spencertől származik, aki megmutatta,
hogy egy n elemű, n részhalmazt tartalmazó rendszer diszkrepanciája
legfeljebb 6n^{1/2} lehet. Bizonyítása azonban nem konstruktív és csak
közel 30 év elteltével születtek meg az első algoritmikus bizonyítások
(Bansal, ill Lovett-Meka). Később Rothvoss egy új, nagyon elegáns
algoritmust adott, melyben a kérdést egy konvex optimalizálási
feladatra vezette vissza.
A diszkrepancia elméletnek rengeteg alkalmazása ismert, előadásomban
ezek közül szeretnék néhányat bemutatni a kombinatorikus optimalizálás
területéről.