A kombinatorika szeminárium következő 2 előadása
<P><CENTER>
               november 21. (péntek)
</CENTER>
<P>
 10:00, Szőkefalvi-Nagy terem: Markó Roland (Universitat Bonn)
<P>
15:00, Haar terem: Simonyi Gábor (Rényi Intézet)


<P><CENTER>
Markó Roland: 
<B>Nemdeterminisztikusan tesztelhető gráf paraméterek</B>
</CENTER>

<P>
Egy gráf paramétert tesztelhető, amennyiben megfelelő mértékben
becsülhető az értéke minden egyszerű G gráfra azon információ
alapján, amit $G$ egy korlátos méretű uniforman véletlenül
kiválasztott feszített részgráfjából nyerünk. Az f gráf
paramétert nemdeterminisztikusan tesztelhetőnek nevezünk, ha
léteznek k és m pozitív egészek (m \leq k) és egy g
"tanúsítvány" paraméter, ami k-élszínezett gráfok paramétere
és őmaga tesztelhető, továbbá minden G-re f(G)=\max g(G'), ahol a
maximum azokon az élszínezett G'-kon fut, amelyekből ha töröljük
az m-nél nagyobb címkéjű színekkel ellátott éleket és a többi
él színéről megfeledkezünk, akkor éppen G-t látjuk.

<P>
A két tesztelhetőségi fogalom kapcsolatáról fogok beszélni,
különösképpen arról, hogy a tesztelhetőséghez szükséges
mintaméret hogyan becsulhető felülről, ha ismerjük a
tanusítvány által megkövetelt mintaméretet.

<P><CENTER>
Simonyi Gábor: 
<B>Lokális kromatikus szám</B>
</CENTER>

<P>
A címben szereplő fogalmat Erdős Pál, Füredi Zoltán, Hajnal
András, Komjáth Péter, Vojtech Rödl és Seress Ákos egy 1986-ban
megjelent cikke vezette be.  Ez a színezési paraméter azt méri,
hogy hány színnek kell feltetlenül előfordulnia a legtarkább
(zárt) csúcsszomszédságban, ha a gráfot jól színezzük. A
színezés nem kell, hogy optimális legyen, használhatunk a
kromatikus számnal több színt is. Meglepő módon érdemes is
többet használni, létezik olyan gráf, ami sok színnel
színezhető jól úgy, hogy minden csúcs a sajátjan kívül csak
legfeljebb két színt "lásson" a szomszédain (ez azt mutatja, hogy
lokális kromatikus száma legfeljebb 3), míg a kromatikus száma
tetszőlegesen nagy. Az előadás néhány az utóbbi években elért,
a lokális kromatikus számmmal kapcsolatos eredményt próbál
összefoglalni.

<P>
Az előadás alapjául szolgáló eredmények a következő kollegák
különböző részhalmazaival közös dolgozatokban szerepelnek:
Körner János, Bojan Mohar, Concetta Pilotto, Tardos Gábor, Sinisa
Vrecica, Zsbán Ambrus.

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

<P>
Péter

<P>
<IMG SRC="infoblokk_kedv_final_magyar.jpg" height="61">
<IMG SRC="szte_cimer.jpg" height="61">
<IMG SRC="Szechenyi2020.jpg" height="61">
<P>
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"