A következő (extra) kombinatorika szeminárium ideje


<P><CENTER>
    július 11. (csütörtök), 10:00,
</CENTER>


helye a szokásossá váló


<P><CENTER>
    Kalmár-Intézet, Árpád tér, szemináriumi szoba (második emeletet, a
    folyosó vége)
</CENTER>


és előadása:



<P><CENTER>Markó Roland (University of Bonn):
<B>Hatékonyan tesztelhető gráfparaméterek</B>
</CENTER>


<P>
Tesztelhetőnek nevezünk egy gráfparamétert, amennyiben bármely gráf
esetében, bármilyen kicsi előre adott epszilon hibával tudjuk közelíteni
additív értelemben az értéket kizárólag egy uniform véletlen módon
kiválasztott csúcshalmazon feszített részgráfon felvett érték segítségével
nagy valószínűséggel, ahol a véletlen csúcshalmaz méretére egy csak
epszilontol  függő felső korlátunk van. Hatékonyság alatt pedig azt értjük,
hogy ez az említett felső korlát polinomiális epszilon reciprokában.
A maximális vágás sűrűsége hatékonyan tesztelhető, ez Alon, de la Vega,
Karpinski és Kannan eredménye. Ennek a bizonyításáról fogok beszélni,
továbbá az analóg állításról általánosított alapállapoti energiákra.

<P>
Minden érdeklődőt szeretettel várunk,

<P>
Péter

<P>

<P>

<IMG SRC="Infoblokk2_ESZA_egyes.jpg" height="61">
<IMG SRC="szte_cimer.jpg" height="61">
<IMG SRC="USZT_logo_cmyk.jpg" height="61">
<P>
Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073,
Telemedicine Oriented Research in the Fields of Mathematics,
Informatics and Medical Sciences