A kombinatorika szeminárium következő előadása

Az előadás:

n-változós Boole-függvények felfoghatók mint az n-dimenzios kocka csúcsainak piros/kék színezése. Ha adott az n-dimenzios térben egy piros/kék ponthalmaz úgy, hogy a hiperkocka minden csúcsához egyértelmű a legközelebbi pont, akkor ez alapján egy Boole-függvény határozható meg: Minden csúcs színét a ponthalmazunkból a legközelebbi pont színe adja.

Ha páratlan dimenzióban egy piros pontot rakunk (0,0,...,0)-be és egy kéket (1,1,...,1)-be, akkor a `többség' függvényt reprezentáljuk egy két pontú halmazzal. Nyilvánvaló, hogy minden Boole-függvény reprezentálható alkalmas színezett halmazzal. Milyen kevés pont kell egy függvényhez? Konkrét függvény esetén milyen alsó korlátokat tudunk adni?

Minden érdeklődőt szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073 projekt, "Telemedicina fókuszú kutatások Orvosi, Matematikai és Informatikai tudományterületeken"