Tardos Gabor:
Grafhomomorfizmusok, dualitasok es regularis fa-halmazok
<br><br>
Veges iranyitott grafok kozti homomorfizmusokat vizsgalunk.
Egy G -> H grafhomomorfizmus G csucsait H csucsaiba kepezi ugy, 
hogy el
kepe el. Ha P_k a k elu iranyitott ut es D_k a k csucsu 
tranzitiv
tournament, akkor tetszoleges G iranyitott grafra a P_k -> G es 
G -> D_k
homomorfizmusoknak pont az egyike letezik. Ilyesmit ir le a 
"dulais par"
fogalma: a grafosztalyokbol allo (F,D) part dualis parnak 
nevezzuk, ha a
(i) letezik F-beli f es egy f -> G homomorfizmus es a
(ii) letezik D-beli d es egy G -> d homomorfizmus
allitasok kozul minden (veges iranyitott) G grafra pont az 
egyik teljesul.
<br><br>
Antilanc dualitasrol akkor beszelunk, ha az F es D halmazok a
homomorfizmusra nezve antilancot alkotnak (egyik elemnek sincs
homomorfizmyusa egy masikra).
<br><br>
A dualis parokat, ahol F es D veges Foniok, Nesetril es Tardif
karakterizaltak, mig az F veges, D vegtelen antilanc esetet 
Erdos Peter es
Soukup Lajos kizartak. Mi a D veges, F vegtelen antilanc 
esettel 
foglalkozunk.
Ilyen parok vannak, es annak meghatarozasa, hogy mely F 
vegtelen
antilancnak van veges dualisa a regularis nyelv fogalmanak egy 
erdekes
altalanositasara vezet iranyitott fak osztalyaira. Ha csak utak 
(nem
konzisztens) iranyitasakent eloallo grafokbol all F, akkor 
visszakapjuk a
regularis nyelv ismert fogalmat: ha az F-beli utakat a {+,-} 
feletti
szavakkal azonositva (+=elore, -=vissza) regularis nyelvet 
kapunk, akkor
van egy d veges iranyitott graf, hogy (F,{d}) dualis par.
<br><br>
Az eredmenyek Erdos Peterrel es Claude Tardiffal kozosek.